HDU 5547 Sudoku（dfs）
题意：给你一个4*4的方阵，里面包含的字符是1到4，还有*，然后要求把所有的*都替换成1到4，要求是每个上下左右四个2*2的小方阵里面1到4都要有，每一行每一列的数字不能相同，规则有点像数独。
思路：因为只有4*4，所以直接用dfs爆搜，然而也不能太暴力，直接搜到底再判断矩阵符不符合条件，这样太暴力了以至于最后一个样例都不能秒出，所以，要在每次给*赋值的时候判断是否能放这个数字，直接判断所在行和所在列有没有一样的就行了。然后到了最后，再判断这个矩阵符不符合条件。
P.S.一开始就是很傻地搜到底了再判断，以至于最后一个例子没有秒出，然后加了中间的判断之后，有个例子陷入了死循环，那就是当矩阵都是*的时候，最后一个*赋值之后没有条件进入下一步dfs了，然后就死循环了，改过就好了。然后dfs写得好挫啊，都写了两百多行了，然而不想重新写了······
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #include<map> 10 #include<stack> 11 #include<set> 12 #define ll long long 13 #define maxn 100010 14 #define PI acos(-1.0) //圆周率 15 const ll INF = 1e18; 16 const int len=30; 17 using namespace std; 18 int T,flag; 19 int f[10][10]; 20 char s[10][10]; 21 int biao[10]; 22 int ff[4][2]={0,0,0,1,1,0,1,1}; 23 int kk[4][2]={0,1,0,-1,1,0,-1,0}; 24 bool judge1(int a,int b) 25 { 26 memset(biao,0,sizeof(biao)); 27 28 for(int i=0;i<4;i++) 29 { 30 int l=a+ff[i][0]; 31 int r=b+ff[i][1]; 32 33 biao[s[l][r]-'0']++; 34 if(biao[s[l][r]-'0']>1) return false; 35 } 36 return true; 37 } 38 bool judge2(int a) 39 { 40 memset(biao,0,sizeof(biao)); 41 42 for(int i=0;i<4;i++) 43 { 44 biao[s[a][i]-'0']++; 45 if(biao[s[a][i]-'0']>1) return false; 46 } 47 48 return true; 49 } 50 bool judge3(int b) 51 { 52 memset(biao,0,sizeof(biao)); 53 54 for(int i=0;i<4;i++) 55 { 56 biao[s[i][b]-'0']++; 57 if(biao[s[i][b]-'0']>1) return false; 58 } 59 60 return true; 61 } 62 bool judge4(int a,int b,int v) 63 { 64 for(int i=0;i<4;i++) 65 { 66 if(s[i][b]-'0'==v) return false; 67 } 68 for(int i=0;i<4;i++) 69 { 70 if(s[a][i]-'0'==v) return false; 71 } 72 73 return true; 74 } 75 bool jud(int a,int b) 76 { 77 if(a>=0&&a<4&&b>=0&&b<4) return true; 78 else return false; 79 } 80 bool prin() 81 { 82 if(judge1(0,0)&&judge1(0,2)&&judge1(2,0)&&judge1(2,2)) 83 { 84 if(judge2(0)&&judge2(1)&&judge2(2)&&judge2(3)) 85 { 86 if(judge3(0)&&judge3(1)&&judge3(2)&&judge3(3)) return true; 87 } 88 } 89 return false; 90 } 91 void dfs(int a,int b,int cnt) 92 { 93 if(flag||!jud(a,b)||f[a][b]) return ; 94 95 if(!cnt) 96 { 97 if(prin()) 98 { 99 for(int i=0;i<4;i++) printf("%s ",s[i]); 100 flag=1; 101 return ; 102 } 103 else return ; 104 } 105 106 if(s[a][b]=='*') 107 { 108 for(int i=1;i<=4;i++) 109 { 110 if(judge4(a,b,i)) 111 { 112 s[a][b]=i+'0'; 113 cnt-=1; 114 if(!cnt) dfs(a,b,cnt); 115 f[a][b]=1; 116 for(int j=0;j<4;j++) 117 { 118 int l=a+kk[j][0]; 119 int r=b+kk[j][1]; 120 if(jud(l,r)&&!f[l][r]) dfs(l,r,cnt); 121 } 122 cnt+=1; 123 s[a][b]='*'; 124 f[a][b]=0; 125 } 126 } 127 } 128 else 129 { 130 f[a][b]=1; 131 for(int j=0;j<4;j++) 132 { 133 int l=a+kk[j][0]; 134 int r=b+kk[j][1]; 135 if(jud(l,r)&&!f[l][r]) dfs(l,r,cnt); 136 } 137 f[a][b]=0; 138 } 139 140 return ; 141 } 142 int main() 143 { 144 int cas=0; 145 scanf("%d",&T); 146 while(T--) 147 { 148 for(int i=0;i<4;i++) scanf("%s",s[i]); 149 150 int sum=0; 151 flag=0; 152 for(int i=0;i<4;i++) 153 { 154 for(int j=0;j<4;j++) 155 { 156 if(s[i][j]=='*') sum++; 157 } 158 } 159 160 printf("Case #%d: ",++cas); 161 for(int i=0;i<4;i++) 162 { 163 for(int j=0;j<4;j++) 164 { 165 if(s[i][j]=='*') 166 { 167 dfs(i,j,sum); 168 if(flag) break; 169 } 170 } 171 if(flag) break; 172 } 173 } 174 175 return 0; 176 }