好难的搜索题
注意的细节
1. 对于每行、每列、每个九宫格,分别用一个9位的二进制数(全局整数变量)保存哪些数字还可以填,1表示还可以填,0表示不可以填
2. 对于每个位置,把它所在行、列、九宫格的3个二进制数做与运算,就可以得到这个位置上还可以填哪些数字,用lowbit运算就可以把能填的数字取出。
3. 当一个位置填上某个数后,把该位置所在的行、列、九宫格记录的二进制数的对应位改成0,即可更新当前状态;回溯时改回1即可还原现场
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];
void init()
{
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;
}
}
}
int lowbit(int x)
{
return x & -x;
}
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 is_set)
{
if(is_set) str[x * N + y] = '1' + t;
else str[x * N + y] = '.';
int v = 1 << t;
if(!is_set) v = -v;
row[x] -= v;
col[y] -= v;
cell[x / 3][y / 3] -= v;
}
bool dfs(int cnt)
{
if(!cnt) return true;
int minv = 10;
int x, y;
for(int i = 0; i < N; i ++){
for(int j = 0; j < N; j ++){
if(str[i * N + j] == '.'){
int state = get(i, j);
if(minv > ones[state]){
minv = 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(cnt - 1)) return true;
draw(x, y, t, false);
}
return false;
}
int main()
{
for(int i = 0; i < N; i ++) map[1 << i] = i;
for(int i = 0; i < 1 << N; i ++){
for(int j = 0; j < N; j ++){
ones[i] += i >> j & 1;
}
}
while(cin >> str, str[0] != 'e'){
init();
int cnt = 0;
for(int i = 0, k = 0; i < N; i ++){
for(int j = 0; j < N; j ++, k ++){
if(str[k] != '.'){
int t = str[k] - '1';
draw(i, j, t, true);
}else cnt ++;
}
}
dfs(cnt);
puts(str);
}
return 0;
}
求关注