AcWing 166. 数独
原题链接
中等
作者:
小.bug
,
2022-05-17 01:10:41
,
所有人可见
,
阅读 205
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
int ones[1 << N], pos[1 << N];
int col[N],row[N],g[3][3];
string s;
int lowbit(int x)
{
return x & -x;
}
int get(int i, int j)
{
return row[i] & col[j] & g[i / 3][j / 3];
}
bool dfs(int cnt)
{
if(cnt == 0) return true;
int minv = 10;
int sx, sy;
for(int i = 0, k = 0; i < N; i++)
{
for(int j = 0; j < N; j++, k++)
{
if(s[k] == '.')
{
if(ones[get(i,j)] < minv)
{
minv = ones[get(i,j)];
sx = i;
sy = j;
}
}
}
}
//从(sx,sy)开始
for(int i = get(sx,sy); i; i -= lowbit(i))
{
int t = pos[lowbit(i)];
s[sx * 9 + sy] = '1' + t;
row[sx] -= (1 << t);
col[sy] -= (1 << t);
g[sx / 3][sy / 3] -= (1 << t);
if(dfs(cnt - 1)) return true;
g[sx / 3][sy / 3] += (1 << t);
col[sy] += (1 << t);
row[sx] += (1 << t);
s[sx * 9 + sy] = '.';
}
return false;
}
void init()
{
for(int i = 0; i < N; i++) col[i] = row[i] = (1 << N) - 1;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
g[i][j] = (1 << N) - 1;
}
}
}
int main()
{
for(int i = 0; i < N; i++) pos[1 << i] = i;
for(int i = 0; i < 1 << N; i++)
{
int k = 0;
for(int j = i; j; j -= lowbit(j)) k++;
ones[i] = k;
}
while(cin >> s && s[0] != 'e')
{
init();
int cnt = 0;
for(int i = 0,k = 0; i < N; i++)
{
for(int j = 0; j < N; j++,k++)
{
if(s[k] != '.')
{
int t = s[k] - '1';
row[i] -= (1 << t);
col[j] -= (1 << t);
g[i / 3][j / 3] -= (1 << t);
}
else cnt ++;
}
}
dfs(cnt);
cout << s << endl;
}
return 0;
}