题解：B4279 [蓝桥杯青少年组国赛 2023] 数独填数
__Groyhj__QwQ
·
·
题解
B4279 [蓝桥杯青少年组国赛 2023] 数独填数 题解
本题与 P1784 在输入输出略有不同外，思路完全一样。
1. 思路分析
这道题其实就是数独。
首先，我们应该知道填入空格的数应满足三点条件：
- 每一行包含数字 1 \sim 9 且不重复；
- 每一列包含数字 1 \sim 9 且不重复；
- 每一个 3 \times 3 方块包含数字 1 \sim 9 且不重复。
对于第一点，我们可以定义一个 bool 数组 b，其中 b_{i,j}=1 用来表示第 i 行的 j(1 \le j \le 9) 已经出现过。
对于第二点，我们也可以定义一个 bool 数组 c，其中 c_{i,j}=1 用来表示第 i 列的 j(1 \le j \le 9) 已经出现过。
对于第三点，就比较复杂，我们先将整个网格分成 9 个 3 \times 3 的方块，再定义一个 bool 数组 d，其中 d_{i,j}=1 用来表示第 i 个 3 \times 3 方块的 j(1 \le j \le 9) 已经出现过。
然后，我们用 DFS 搜索每一个空格，对于空格 (x,y)，它在第 z 个 3 \times 3 方块，枚举 i(1 \le i \le 9)，如果 i 在
最后，当所有空格都填上了符合要求的数字时，输出完成的数独。
### 2. AC 代码
[AC 记录](https://www.luogu.com.cn/record/216421523)。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[11][11];
bool b[11][11], c[11][11], d[11][11];
int f(int x, int y) { // 查找 (x,y) 在第几个小方块
if (x <= 3 && y <= 3) return 1;
if (x <= 3 && y <= 6) return 2;
if (x <= 3 && y <= 9) return 3;
if (x <= 6 && y <= 3) return 4;
if (x <= 6 && y <= 6) return 5;
if (x <= 6 && y <= 9) return 6;
if (x <= 9 && y <= 3) return 7;
if (x <= 9 && y <= 6) return 8;
if (x <= 9 && y <= 9) return 9;
}
void out() { // 输出
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
// /* B4279
cout << a[i][j];
// */
/* P1784
cout << a[i][j] << " ";
*/
}
cout << endl;
}
exit(0);
}
void dfs(int x, int y) {
if (a[x][y] != 0) {
if (x == 9 && y == 9) out(); // 搜索下一个空格，搜索完便输出
else if(y == 9) dfs(x + 1, 1);
else dfs(x, y + 1);
} else {
for (int i = 1; i <= 9; i++) {
if ((!b[x][i]) && (!c[y][i]) && (!d[f(x, y)][i])) {
a[x][y] = i;
b[x][i] = c[y][i] = d[f(x, y)][i] = 1;
if (x == 9 && y == 9) out(); // 同上
else if (y == 9) dfs(x + 1, 1);
else dfs(x, y + 1);
a[x][y] = 0;
b[x][i] = c[y][i] = d[f(x, y)][i] = 0;
}
}
}
}
signed main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) { // 输入
// /* B4279
char t;
cin >> t;
if (t != '.') {
int tt = t-'0';
b[i][tt] = c[j][tt] = d[f(i, j)][tt] = 1;
a[i][j] = tt;
} else {
a[i][j] = 0;
}
// */
/* P1784
int t;
cin >> t;
if (t != 0) {
b[i][t] = c[j][t] = d[f(i, j)][t] = 1;
a[i][j] = t;
} else {
a[i][j] = 0;
}
*/
}
}
dfs(1, 1);
return 0;
}
```