首页 > 代码库 > poj2676(Sudoku)
poj2676(Sudoku)
题目地址：Sudoku
题目大意：
一个9*9的矩阵，让你往里面填写数字，以保证每行每列以及9*9分解的9个小3*3的矩阵里 数字1-9不重复。如果有多种情况，输出其中一种即可。
解题思路：
暴搜DFS。正着搜600+ms 。倒着搜0ms。 数据的原因。因为少写了一句话，让我调试了一下午。
分析：
我是用ce2标记该空是否能找到合适的数，如果找不到return到上一层，这时的ce2 还是为“1”（意思为该坐标内有值），没重新归零，这样以至于将1-9循环完之后进不去
if（！ce2） 。这样就没法return 到上一层。所以DFS之后应该将ce2归零。
正着搜代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 char map1[10][10]; 44 int map[10][10]; 45 int vis1[10][10],vis2[10][10],vis3[10][10]; 46 int cnt; 47 int ce; 48 int ce1; 49 int DFS(int x,int y,int cnt) 50 { 51 int i,j,k,h1,h2; 52 if (cnt==81) 53 { 54 ce1=1; 55 return 0; 56 } 57 for(i=x;i<=9;i++) 58 for(j=y;j<=9;j++) 59 { 60 if (j==9) 61 y=1; 62 if (!map[i][j]) 63 { 64 int ce2=0; 65 for(k=1;k<=9;k++) 66 { 67 if (vis1[i][k]||vis2[j][k]) 68 continue; 69 for(ce=0,h1=(i-1)/3*3+1;h1<=(i-1)/3*3+3;h1++) 70 { 71 for(h2=(j-1)/3*3+1;h2<=(j-1)/3*3+3;h2++) 72 if (k==map[h1][h2]) 73 { 74 ce=1; 75 break; 76 } 77 if (ce) 78 break; 79 } 80 if (ce) 81 continue; 82 ce2=1; 83 vis1[i][k]=1; 84 vis2[j][k]=1; 85 map[i][j]=k; 86 DFS(i,j,cnt+1); 87 if (ce1) 88 return 0; 89 vis1[i][k]=0; 90 vis2[j][k]=0; 91 map[i][j]=0; 92 ce2=0; 93 } 94 if (!ce2) 95 return 0; 96 } 97 } 98 return 0; 99 }100 int main()101 {102 int cas;103 scanf("%d",&cas);104 while(cas--)105 {106 int i,j;107 cnt=0;108 memset(map,0,sizeof(map));109 memset(map1,0,sizeof(map1));110 memset(vis1,0,sizeof(vis1));111 memset(vis2,0,sizeof(vis2));112 memset(vis3,0,sizeof(vis3));113 for(i=1;i<=9;i++)114 {115 getchar();116 for(j=1;j<=9;j++)117 {118 scanf("%c",&map1[i][j]);119 map[i][j]=map1[i][j]-‘0‘;120 int cc=map[i][j];121 if (map[i][j])122 {123 vis1[i][cc]=1;124 vis2[j][cc]=1;125 cnt++;126 }127 }128 }129 ce1=0;130 DFS(1,1,cnt);131 for(i=1;i<=9;i++)132 {133 for(j=1;j<=9;j++)134 printf("%d",map[i][j]);135 printf("\n");136 }137 }138 return 0;139 }140 /*141 10142 103628000143 002139468144 980000231145 391500786146 468917352147 000863914148 237480000149 619000000150 854390000151 */
倒着搜代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 #define PI 3.1415927 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {0,-1,0,1}; 26 const int d1y[]= {-1,0,1,0}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 const int dirx[]= {-1,1,-2,2,-2,2,-1,1}; 32 const int diry[]= {-2,-2,-1,-1,1,1,2,2}; 33 /*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/ 34 /***************************************/ 35 void openfile() 36 { 37 freopen("data.in","rb",stdin); 38 freopen("data.out","wb",stdout); 39 } 40 priority_queue<int> qi1; 41 priority_queue<int, vector<int>, greater<int> >qi2; 42 /**********************华丽丽的分割线,以上为模板部分*****************/ 43 char map1[10][10]; 44 int map[10][10]; 45 int vis1[10][10],vis2[10][10],vis3[10][10]; 46 int cnt; 47 int ce; 48 int ce1; 49 int DFS(int x,int y,int cnt) 50 { 51 int i,j,k,h1,h2; 52 if (cnt==81) 53 { 54 ce1=1; 55 return 0; 56 } 57 for(i=x;i>=1;i--) 58 for(j=y;j>=1;j--) 59 { 60 if (j==1) 61 y=9; 62 if (!map[i][j]) 63 { 64 int ce2=0; 65 for(k=1;k<=9;k++) 66 { 67 if (vis1[i][k]||vis2[j][k]) 68 continue; 69 for(ce=0,h1=(i-1)/3*3+1;h1<=(i-1)/3*3+3;h1++) 70 { 71 for(h2=(j-1)/3*3+1;h2<=(j-1)/3*3+3;h2++) 72 if (k==map[h1][h2]) 73 { 74 ce=1; 75 break; 76 } 77 if (ce) 78 break; 79 } 80 if (ce) 81 continue; 82 ce2=1; 83 vis1[i][k]=1; 84 vis2[j][k]=1; 85 map[i][j]=k; 86 DFS(i,j,cnt+1); 87 if (ce1) 88 return 0; 89 vis1[i][k]=0; 90 vis2[j][k]=0; 91 map[i][j]=0; 92 ce2=0; //因为没加这一句话调了一下午，现在终于吸取教训了！！！ 93 } 94 if (!ce2) 95 return 0; 96 } 97 } 98 return 0; 99 }100 int main()101 {102 int cas;103 scanf("%d",&cas);104 while(cas--)105 {106 int i,j;107 cnt=0;108 memset(map,0,sizeof(map));109 memset(map1,0,sizeof(map1));110 memset(vis1,0,sizeof(vis1));111 memset(vis2,0,sizeof(vis2));112 memset(vis3,0,sizeof(vis3));113 for(i=1;i<=9;i++)114 {115 getchar();116 for(j=1;j<=9;j++)117 {118 scanf("%c",&map1[i][j]);119 map[i][j]=map1[i][j]-‘0‘;120 int cc=map[i][j];121 if (map[i][j])122 {123 vis1[i][cc]=1;124 vis2[j][cc]=1;125 cnt++;126 }127 }128 }129 ce1=0;130 DFS(9,9,cnt);131 for(i=1;i<=9;i++)132 {133 for(j=1;j<=9;j++)134 printf("%d",map[i][j]);135 printf("\n");136 }137 }138 return 0;139 }140 /*141 10142 103628000143 002139468144 980000231145 391500786146 468917352147 000863914148 237480000149 619000000150 854390000151 */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。