dfs写法技巧:
1.
line[i][num]表示第i行是否出现数字num;
col[j][num]表示第j列是否出现数字num;
cell[i][j][num]表示第i行j列小格子内是否出现数字num;
这样写可以避免繁杂的检查
2.
dfs返回值设为bool类型可以在找到结果后快速退出
总结:
闫总tql、题是经典中的经典
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 15;
char map[N][N];
bool line[N][N],col[N][N],cell[3][3][N];
bool dfs (int x, int y) {
if (y == 9) x++,y = 0;
if (x == 9) {
for (int i = 0;i < 9;i++) cout << map[i] << endl;
return true;
}
if (map[x][y] != '.') return dfs(x,y + 1);
for (int i = 1;i <= 9;i++) {
if (!line[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
map[x][y] = i + '0';
line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
if (dfs(x,y + 1)) return true;
line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
map[x][y] = '.';
}
}
return false;
}
int main () {
for (int i = 0;i < 9;i++) {
cin >> map[i];
for (int j = 0;j < 9;j++) {
if (map[i][j] != '.') {
int num = map[i][j] - '0';
line[i][num] = col[j][num] = cell[i / 3][j / 3][num] = true;
}
}
}
dfs(0,0);
}