AcWing 166. 数独(DFS剪枝 + 位运算)
原题链接
中等
作者:
只拉臭屎
,
2024-03-11 10:40:29
,
所有人可见
,
阅读 17
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], mp[M];
char str[100];
int col[N], row[N], cell[4][4];// 块就像坐标一样记录比较方便
void init()
{
for (int i = 0; i < 9; i ++) col[i] = row[i] = (1 << 9) - 1;
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 3; j ++)
cell[i][j] = (1 << 9) - 1;
}
void draw(int x, int y, char t)
{
int a = str[x * 9 + y] - '1';// ***
str[x * 9 + y] = t;
bool is_set = true;
if (t == '.') is_set = false;
if(is_set) a = t - '1';
int v = 1 << a;
if (!is_set) v = -v;
col[y] -= v;
row[x] -= v;
cell[x/3][y/3] -= v;
}
int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}
int lowbit(int x)
{
return x & -x;
}
bool dfs(int cnt)
{
if (!cnt) return true;
// 优化搜索顺序, 找到分支最少的点
int x, y;
int minv = 10;
for (int i = 0; i < 9; i ++)
for (int j = 0; j < 9; j ++)
{
if (str[i * 9 + j] == '.')
{
int state = get(i, j);
if (ones[state] < minv)
{
minv = ones[state];
x = i, y = j;
}
}
}
// 开始搜索
int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = mp[lowbit(i)];// 第几位是1
draw(x, y, t + '1');
if (dfs(cnt - 1)) return true;// 可行性剪枝, 一旦不成功就不用继续
draw(x, y, '.');
}
return false;
}
int main()
{
for (int i = 0; i < 9; i ++) mp[1 << i] = i;
for (int i = 0; i < M; i ++)
for (int j = 0; j < 9; j ++)
ones[i] += (i >> j) & 1;
while (cin >> str, str[0] != 'e')
{
init();
int cnt = 0;// 记录需要填的格子数量
for (int i = 0; i < 9; i ++)
for (int j = 0; j < 9; j ++)
{
char t = str[i * 9 + j];
if (t != '.')
draw(i, j, t);
else
cnt ++;
}
dfs(cnt);
puts(str);
}
}