POJ 2676

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string>
  4 #define MAXN 9
  5 using namespace std;
  6 
  7 bool mark_o[MAXN][MAXN];
  8 bool mark[MAXN+1][MAXN+1];
  9 bool mark_j[MAXN+1][MAXN+1];
 10 bool mark_3_3[MAXN+1][MAXN+1];
 11 int _m[MAXN][MAXN];
 12 bool boo;
 13 void dfs(int i,int j);
 14 int get_place(int i,int j);
 15 int main()
 16 {
 17    // freopen("acm.acm","r",stdin);
 18    // freopen("out.acm","w",stdout);
 19     //int r;
 20     //int c;
 21     int i;
 22     int j;
 23     int tem;
 24     int test;
 25     string s;
 26     cin>>test;
 27     while(test --)
 28     {
 29         memset(mark_o,false,sizeof(mark_o));
 30         memset(mark,false,sizeof(mark));
 31         memset(mark_j,false,sizeof(mark_j));
 32         memset(mark_3_3,false,sizeof(mark_3_3));
 33         for(i = 0; i < MAXN; ++ i)
 34         {
 35             cin>>s;
 36             for(j = 0; j < MAXN; ++ j)
 37             {
 38                 _m[i][j] = s[j] - '0';
 39                 if( (tem = s[j]-'0') != 0)
 40                 {
 41                     mark_o[i][j] = true;
 42                     mark_j[j][s[j] - '0'] = true;
 43                     mark[i][s[j] - '0'] = true;
 44                     mark_3_3[get_place(i,j)][tem] = true;
 45                 }
 46             }
 47         }
 48         boo = false;
 49         for(i = 0; i < MAXN; ++ i)
 50         {
 51               if(!mark_o[0][i])
 52               {
 53                       break;
 54               }
 55         }
 56         dfs(0,i);
 57         
 58     }
 59     return 0;
 60 }
 61 
 62 
 63 void dfs(int i,int j)
 64 {
 65     if(i == 9)
 66     {
 67         int m;
 68         int n;
 69         for(m = 0; m < 9; ++ m)
 70         {
 71             for(n = 0; n < 9; ++ n)
 72             {
 73                 cout<<_m[m][n];
 74             }
 75             cout<<endl;
 76         }
 77         boo = true;
 78         return;
 79     }
 80     if(j == 9)
 81     {
 82             int _i;
 83             for( _i = 0; _i < 9; ++ _i)
 84             {
 85                 if(!mark_o[i+1][_i])
 86                 {
 87                     break;
 88                 }
 89             }
 90             dfs(i+1,_i);
 91             if(boo)
 92             {
 93                 return;
 94             }
 95     }
 96     for(int k = 1;  k < 10; ++ k)
 97     {
 98         int place = get_place(i,j);
 99         if(!mark_j[j][k] && !mark[i][k] && !mark_o[i][j] && !mark_3_3[place][k] )
100         {
101             _m[i][j] = k;
102             mark[i][k] = true;
103             mark_j[j][k] = true;
104             mark_o[i][j] = true;
105             mark_3_3[place][k] = true;
106             int _j;
107             for(_j = j; _j < 9; ++ _j)
108             {
109                 if(!mark_o[i][_j])
110                 {
111                     break;
112                 }
113             }
114             dfs(i,_j);
115             mark_3_3[place][k] = false;
116             mark_o[i][j] = false;
117             mark[i][k] = false;
118             mark_j[j][k] = false;
119         
120             if(boo)
121                 return;
122         }
123     }
124 }
125 
126 int get_place(int i,int j)
127 {
128     if(i >= 0 && i <= 2)
129     {
130         if(j >= 0 && j <= 2)
131         {
132             return 0;
133         }
134         else if(j >= 3 && j <= 5)
135         {
136             return 1;
137         }
138         else
139         {
140             return 2;
141         }
142     }
143     else if(i >= 3 && i <= 5)
144     {
145         if(j >= 0 && j <= 2)
146         {
147             return 3;
148         }
149         else if(j >= 3 && j <= 5)
150         {
151             return 4;
152         }
153         else
154         {
155             return 5;
156         }
157     }
158     else if(i >= 6 && i <= 8)
159     {
160         if(j >= 0 && j <= 2)
161         {
162             return 6;
163         }
164         else if(j >= 3 && j <= 5)
165         {
166             return 7;
167         }
168         else 
169         {
170             return 8;
171         }
172     }
173 }