AcWing 1613. 数独简单版
原题链接
简单
作者:
我要出去乱说
,
2021-02-06 21:32:37
,
所有人可见
,
阅读 398
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
char g[N][N];
bool row[N][N], col[N][N], cell[3][3][N]; //记录每行、每列、每个九宫格中数字1~9的使用情况
bool dfs(int x, int y)
{
if (y == 9) x ++ , y = 0; //这一行填完,开始下一行
if (x == 9) //最后一行填完,输出结果
{
for (int i = 0; i < 9; i ++ ) cout << g[i] << endl;
return true;
}
if (g[x][y] != '.') return dfs(x, y + 1); //当前格为数字,不用填,去下一格
for (int i = 0; i < 9; i ++ ) //遍历1~9,判断当前格能填哪个数
if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
{
g[x][y] = i + '1';
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
if (dfs(x, y + 1)) return true;
//还原现场,当该方案走不通时需要回退,回退时需要还原现场
row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
g[x][y] = '.';
}
return false; //找不到方案,退回上一层递归
}
int main()
{
for (int i = 0; i < 9; i ++ )
{
cin >> g[i];
for (int j = 0; j < 9; j ++ )
if (g[i][j] != '.')
{
int t = g[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
}
dfs(0, 0); //从第0行0列开始
return 0;
}