Sudoku
Problem's Link: http://poj.org/problem?id=2676
Mean:
略
analyse:
记录所有空位置，判断当前空位置是否可以填某个数，然后直接DFS，注意从后往前搜索，时间比正向搜快很多。16ms水过
Time complexity: O(n)
Source code:
// Memory Time // 1347K 0MS // by : crazyacking // 2015-04-10-14.30 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; struct Node { int x,y; }; Node b[100]; int g[9][9]; int idx; bool flag; void input() { char s[10]; idx=0; flag=0; for(int i=0;i<9;++i) { scanf("%s",s); for(int j=0;j<9;++j) { g[i][j]=s[j]-'0'; if(g[i][j]==0) { b[idx].x=i; b[idx].y=j; idx++; } } } idx--; } bool Check(int x,int y,int num) { for(int i=0;i<9;++i) { if(g[x][i]==num) return false; if(g[i][y]==num) return false; } int sta_x=x/3*3; int sta_y=y/3*3; for(int i=sta_x;i<sta_x+3;++i) { for(int j=sta_y;j<sta_y+3;++j) { if(g[i][j]==num) return false; } } return true; } void DFS(int n) { if(n==-1) { flag=1; return ; } int x=b[n].x; int y=b[n].y; for(int i=1;i<=9;++i) { if(Check(x,y,i)) { g[x][y]=i; DFS(n-1); if(flag) return ; g[x][y]=0; } } return; } void output() { for(int i=0;i<9;++i) { for(int j=0;j<9;++j) { printf("%d",g[i][j]); } puts(""); } } int main() { int Cas; scanf("%d",&Cas); while(Cas--) { input(); DFS(idx); output(); } return 0; }
