1 #include<iostream> 2 #include<cstdlib> 3 #include<string> 4 using namespace std; 5 int map[10][10]; 6 int row[10][10]; 7 int col[10][10]; 8 int grid[10][10]; 9 void input() 10![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) { 11 // char a[10]; 12 string a; 13 for(int i=0;i<9;i++) 14![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 15 //getline(cin,a); 16 cin>>a; 17 for(int j=0;j<9;j++) 18![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 19 map[i][j]=a[j]-'0'; 20 if(map[i][j]) 21![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 22 int k=3*(i/3)+j/3; 23 row[i][map[i][j]]=1; //indicates this row has the number map[i][j] 24 col[j][map[i][j]]=1; // 25 grid[k][map[i][j]]=1; 26 } 27 } 28 } 29 } 30 int dfs(int i,int j) 31![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) { 32 int flag=0; 33 if(i==9) 34 return 1; 35 if(map[i][j]) 36![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 37 if(j==8) 38 flag=dfs(i+1,0); 39 else 40 flag=dfs(i,j+1); 41 if(flag) 42 return 1; 43 else 44 return 0; //这里不要改变map的值,起得是一个传递的作用 45 }//在这里如果当前要保存当前递归的信息,如果结果不满足,那么就要回朔,所以设置flag保存此次递归的结果是否可行 46 else 47![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 48 int k=3*(i/3)+j/3; 49 for(int m=1;m<=9;m++) 50![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 51 52 if(!row[i][m]&&!col[j][m]&&!grid[k][m]) 53![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 54 map[i][j]=m; 55 row[i][m]=1; 56 col[j][m]=1; 57 grid[k][m]=1; 58 if(j==8) 59 flag=dfs(i+1,0); 60 else 61 flag=dfs(i,j+1); 62 //如果将}放在这里结束if的话,那么就是错误的答案,因为回朔要紧接着上一次递归进去的位置,这个位置很重要,否则就是错误的答案 63 //在这里如果当前要保存当前递归的信息,如果结果不满足,那么就要回朔,所以设置flag保存此次递归的结果是否可行 64 if(flag) 65 return 1; 66 else //进行回朔 67![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 68 map[i][j]=0; 69 row[i][m]=0; 70 col[j][m]=0; 71 grid[k][m]=0; 72 } 73 }//if 74 }//for 75 } 76 return 0; 77 } 78 void output() 79![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) { 80 for(int i=0;i<9;i++) 81![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { for(int j=0;j<9;j++) 82![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 83 cout<<map[i][j]; 84 } 85 cout<<endl; 86 } 87 } 88 int main() 89![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) { 90 int T; 91 cin>>T; 92 while(T--) 93![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 94 memset(row,0,sizeof(row)); 95 memset(grid,0,sizeof(grid)); 96 memset(col,0,sizeof(col)); 97 input(); 98 dfs(0,0); 99 output(); 100 } 101 system("pause"); 102 } 103![](/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
友情链接
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|