AcWing 166. 数独
原题链接
中等
作者:
总有刁民想害朕
,
2020-05-02 14:03:11
,
所有人可见
,
阅读 1989
思路分析:
一:搜索顺序:
1:随便选择一个空白格
2:枚举该位置可以填的数,然后进入下一层递归
二:优化:
1:优化搜索顺序,每次选择可选择性最小的空白格
2:枚举某个位置可以填什么可以用位运算来进行
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int row[9], col[9], c[3][3];//用来判断行列九宫格哪些位置可用
char str[100];
int m[1<<9], ones[1<<9];//m用来结合lowbit用,ones用来统计有几位1
inline int lowbit(int x){
return x & -x;
}
void init_ones(){
for(int i = 0;i < 1 << 9;++i){
int cnt = 0;
for(int j = i;j > 0;j -= lowbit(j)) ++cnt;
ones[i] = cnt;
}
}
void init_m(){
for(int i = 0;i < 9;++i) m[1 << i] = i;
}
void init_row_col_c(){
for(int i = 0;i < 9;++i) row[i] = col[i] = (1 << 9) - 1;
for(int i = 0;i < 3;++i)
for(int j = 0;j < 3;++j)
c[i][j] = (1 << 9) - 1;
}
inline int get(int x, int y){
return row[x] & col[y] & c[x/3][y/3];
}
bool dfs(int cnt){
if(!cnt) {
//cout << str << endl;
return true;
}
int minv = 9;
int x, y;
for (int i = 0; i < 9; i ++ )
for (int j = 0; j < 9; j ++ )
if (str[i * 9 + j] == '.')
{
int t = ones[get(i, j)];
if (t < minv)
{
minv = t;
x = i, y = j;
}
}
for(int i = get(x, y);i;i -= lowbit(i)){
int t = m[lowbit(i)];
row[x] -= 1 << t;
col[y] -= 1 << t;
c[x/3][y/3] -= 1 << t;
str[x*9+y] = t + '1';
if(dfs(cnt - 1)) return true;
row[x] += 1 << t;
col[y] += 1 << t;
c[x/3][y/3] += 1 << t;
str[x*9+y] = '.';
}
return false;
}
int main(){
init_ones();
init_m();
while(cin >> str && strcmp(str, "end")){
init_row_col_c();
int cnt = 0;
for(int i = 0;i < 9;++i)
for(int j = 0;j < 9;++j)
if(str[i*9+j] != '.'){
int t = str[i*9+j] - '1';
row[i] ^= 1 << t;
col[j] ^= 1 << t;
c[i/3][j/3] ^= 1 << t;
}else ++cnt;
dfs(cnt);
cout << str << endl;
}
return 0;
}
这道题目搜索的时候假如不定义成bool dfs()而是直接用void dfs()去搜会是神马情况?神马情况下dfs要定义成返回bool 类型