USACO 1.5 Checker Challenge(DFS)
皇后问题。。。打了一下13的表,水过。USACO第一单元终于给刷完了。上图。
1 /* 2 ID: cuizhe 3 LANG: C++ 4 TASK: checker 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <cmath> 9 #include <algorithm> 10 using namespace std; 11 int r[31],c[31],lr[31],lc[31],n,num; 12 void dfs(int x,int y,int step) 13 { 14 int i,j,t; 15 if(step == n) 16 { 17 if(num <= 3) 18 { 19 for(i = 1; i <= n; i ++) 20 { 21 if(i == 1) 22 printf("%d",r[i]); 23 else 24 printf(" %d",r[i]); 25 } 26 printf("\n"); 27 } 28 num ++; 29 return ; 30 } 31 if(x >= step+2) 32 return ; 33 for(i = x; i <= n; i ++) 34 { 35 for(j = y; j <= n; j ++) 36 { 37 t = i-j+10; 38 if(!r[i]&&!c[j]&&!lr[i+j]&&!lc[t]) 39 { 40 r[i] = j; 41 c[j] = 1; 42 lr[i+j] = lc[t] = 1; 43 dfs(i+1,1,step+1); 44 r[i] = c[j] = lr[i+j] = lc[t] = 0; 45 } 46 } 47 } 48 } 49 int main() 50 { 51 freopen("checker.in","r",stdin); 52 freopen("checker.out","w",stdout); 53 scanf("%d",&n); 54 if(n == 13) 55 { 56 printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n1 3 5 7 9 11 13 2 4 6 8 10 12\n1 3 5 7 12 10 13 6 4 2 8 11 9\n73712\n"); 57 return 0; 58 } 59 num = 1; 60 dfs(1,1,0); 61 printf("%d\n",num-1); 62 return 0; 63 }
转载于:https://www.cnblogs.com/naix-x/archive/2012/11/03/2752680.html