POJ 2676 && POJ 2918 数独 DFS

题目大意：数独都玩过。。。不多说。。。

思路：简单暴力。预处理行！列！块！中已经出现过的数字，然后就是还有谁。。哼哼。。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; struct node { int x,y; }; bool row[10][10]; bool line[10][10]; bool sti[10][10]; char map[10][10]; vector
       
        loc; void debug() { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { printf("row[%d][%d] = %d,",i,j,row[i][j]); printf("line[%d][%d] = %d,",i,j,line[i][j]); printf("sti[%d][%d] = %d,",i,j,sti[i][j]); puts(""); } } } void init() { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { row[i][j]=line[i][j]=sti[i][j]=false; } } } int getloc(int x,int y) { if(x<=3) { if(y<=3)return 1; else if(y>3&&y<=6)return 2; else return 3; } else if(x<=6&&x>3) { if(y<=3)return 4; else if(y>3&&y<=6)return 5; else return 6; } else { if(y<=3)return 7; else if(y>3&&y<=6)return 8; else return 9; } } bool dfs(int pos) { if(pos>=loc.size())return true; for(int i=1;i<=9;i++) { int Loc=getloc(loc[pos].x,loc[pos].y); if(!row[loc[pos].x][i] && !line[loc[pos].y][i] && !sti[Loc][i]) { // printf("tag = %d\n",i); map[loc[pos].x][loc[pos].y]=i+'0'; row[loc[pos].x][i]=line[loc[pos].y][i]=sti[Loc][i]=true; if(dfs(pos+1))return true; map[loc[pos].x][loc[pos].y]='0'; row[loc[pos].x][i]=line[loc[pos].y][i]=sti[Loc][i]=false; } } return false; } int main() { int T; int CASE=1; scanf("%d",&T); getchar(); while(T--) { init(); loc.clear(); for(int i=1;i<=9;i++) { scanf("%s",map[i]+1); /*for(int j=1;j<=9;j++){ map[i][j]=getchar(); } getchar();*/ } for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { if(map[i][j]=='0') { node tmp; tmp.x=i; tmp.y=j; loc.push_back(tmp); } else row[i][map[i][j]-'0']=true; } } for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) { if(map[j][i]=='0')continue; else line[i][map[j][i]-'0']=true; } } for(int stx=1;stx<=7;stx+=3) { for(int sty=1;sty<=7;sty+=3) { for(int i=stx;i