题解：B4279 [蓝桥杯青少年组国赛 2023] 数独填数

B4279 [蓝桥杯青少年组国赛 2023] 数独填数 题解

本题与 P1784 在输入输出略有不同外，思路完全一样。

1. 思路分析

这道题其实就是数独。

首先，我们应该知道填入空格的数应满足三点条件：

1. 每一行包含数字 $1 \sim 9$ 且不重复；
2. 每一列包含数字 $1 \sim 9$ 且不重复；
3. 每一个 $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$ 在 $b,c,d$ 数组中都没有出现，即 $b_{x,i}=0,c_{y,i}=0,d_{z,i}=0$，那就将空格 $(x,y)$ 暂时设为 $i$，并继续搜索下一个空格；如果没有符合要求的 $i$，就回溯到上一个空格。

最后，当所有空格都填上了符合要求的数字时，输出完成的数独。

2. AC 代码

AC 记录。

#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;
}