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("
");
136         }
137     }
138     return 0;
139 }
140 /*
141 10
142 103628000
143 002139468
144 980000231
145 391500786
146 468917352
147 000863914
148 237480000
149 619000000
150 854390000
151 */

View Code

倒着搜代码：

  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("
");
136         }
137     }
138     return 0;
139 }
140 /*
141 10
142 103628000
143 002139468
144 980000231
145 391500786
146 468917352
147 000863914
148 237480000
149 619000000
150 854390000
151 */

View Code