AcWing 1613. 数独简单版
原题链接
简单
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9, M = 1 << N;
int row[N], col[N], cell[3][3];
int map[M], ones[M];
char g[N][N];
int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}
void draw(int x, int y, int t, bool st)
{
if (st) g[x][y] = t + '1';
else g[x][y] = '.';
int v = 1 << t;
if (!st) v = -v;
row[x] -= v;
col[y] -= v;
cell[x / 3][y / 3] -= v;
}
int lowbit(int x)
{
return x & -x;
}
bool dfs(int u)
{
if (!u) return true;
int min_c = 10;
int x, y;
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
{
if (g[i][j] == '.')
{
int state = get(i, j);
if (ones[state] < min_c)
{
min_c = ones[state];
x = i, y = j;
}
}
}
}
int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = map[lowbit(i)];
draw(x, y, t, true);
if (dfs(u - 1)) return true;
draw(x, y, t, false);
}
return false;
}
int main()
{
int cnt = 0;
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
{
cin >> g[i][j];
}
}
// 预处理一个log数组
for (int i = 0; i < N; i ++) map[1 << i] = i;
// 预处理一个ones数组用来保存所有状态的1的数量
for (int i = 0; i < 1 << N; i ++)
{
for (int j = 0; j < N; j ++)
{
ones[i] += (i >> j & 1);
}
}
// 初始化所有行,所有列,以及所有的3x3网格,使其均为1,表示全部都没有被填入数字
for (int i = 0; i < N; i ++)
{
row[i] = col[i] = (1 << N) -1;
}
for (int i = 0; i < 3; i ++)
{
for (int j = 0; j < 3; j ++)
{
cell[i][j] = (1 << N) - 1;
}
}
// 将已经填好的格子的状态在行列以及网格中去除
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
{
if (g[i][j] != '.')
{
int t = g[i][j] - '1';
draw(i, j, t, true);
}
else cnt ++;
}
}
dfs(cnt);
for (int i = 0; i < N; i ++)
{
for (int j = 0; j < N; j ++)
{
cout << g[i][j];
}
cout << endl;
}
return 0;
}