题面
如下的 10 个格子
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+
填入 0 ~ 9 的数字。
要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
题解
枚举，DFS，剪枝
由上图，我们构建 4 x 6 的矩阵用于存放当前局面下每个位置放置的数字。从 (1, 2) 出发从左到右走到 y == 5 则到下一行，具体行走路线如上图中的紫色线条，最终若能走到 (3, 4) 则为一种有效的方案数。
每当走到一个坐标，枚举剩余没有被使用的数字 i ，且其左边，上边，左上，右上都已经走过了，则数字 i 应该需要与这四个位置的数进行比较看是否存在相邻的情况，若相邻则不可以用当前数字，则需进行剪枝。
详细见代码说明。
答案：
1580
代码
#include<bits/stdc++.h>
using namespace std;
int ans, g[4][6];
void dfs(int x, int y, int state) {
if (x == 3 && y == 4) {
ans++;
return;
}
//state的低 10 位二进制代表了某个数是否已经使用，第 i 位二进制即代表数字 i 是否使用
for (int i = 0; i < 10; i++) {
if (state >> i & 1) continue; //数字 i 被使用过
if (abs(g[x - 1][y] - i) == 1) continue; //上方与当前使用的数相邻
if (abs(g[x - 1][y - 1] - i) == 1) continue; //左上角与当前使用的数相邻
if (abs(g[x - 1][y + 1] - i) == 1) continue; //右上角与当前使用的数相邻
if (abs(g[x][y - 1] - i) == 1) continue; //左方与当前使用的数相邻
int tx = x, ty = y;
if (++ty == 5) tx += 1, ty = 1; //从左向右遍历，若走到了边界，则到下一行最左边
g[x][y] = i;
dfs(tx, ty, state | (1 << i));
}
}
int main() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++) g[i][j] = -100; //初始化为小于 -1 或 大于 10 的数都行
}
dfs(1, 2, 0);
cout << ans << endl;
return 0;
}
| 标题： | 2016年第七届蓝桥杯省赛-F. 方格填数 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/184 |
| 更新： | 2022-09-18 22:46:18 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |