POJ 2488 深搜
要求字典序的順序。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int n,m,cnt; 6 bool success; 7 bool sign[30][30]; 8 int step[30][2]; 9 int dir[8][2]={ 10 -2,-1,-2,1, 11 -1,-2,-1,2, 12 1 ,-2,1 ,2, 13 2 ,-1,2 ,1 14 }; 15 void dfs(int a,int b,int c) //a表示行 b表示列 16 { 17 if(success==1) 18 { 19 20 //printf("fuck\n"); 21 return ; 22 } 23 if(c==m*n) 24 { 25 success=1; 26 return ; 27 } 28 //printf("sadfsda\n"); 29 int t1,t2; 30 for(int i=0;i<8;++i) 31 { 32 t1=a+dir[i][0]; 33 t2=b+dir[i][1]; 34 if(t1>=1&&t1<=n&&t2<=m&&t2>=1&&sign[t1][t2]==0&&success==0) 35 { 36 sign[t1][t2]=1; 37 step[c+1][0]=t1; 38 step[c+1][1]=t2; 39 dfs(t1,t2,c+1); 40 sign[t1][t2]=0; 41 } 42 43 } 44 return; 45 } 46 int main() 47 { 48 int t; 49 bool ok; 50 int count,ccc; 51 while(~scanf("%d",&t)) 52 { 53 ccc=t; 54 count=1; 55 56 while(t--) 57 { 58 //printf("Scenario #%d:",count++); 59 scanf("%d%d",&m,&n); 60 success=0; 61 ok=0; 62 printf("Scenario #%d:\n",count++); 63 64 memset(sign,0,sizeof(sign)); 65 memset(step,0,sizeof(step)); 66 cnt=0; 67 step[1][0]=1; 68 step[1][1]=1; 69 sign[1][1]=1; 70 dfs(1,1,1); 71 if(success) 72 { 73 for(int i=1;i<=m*n;++i) 74 { 75 printf("%c%d",step[i][0]+64,step[i][1]); 76 } 77 78 } 79 else 80 printf("impossible"); 81 if(count==ccc+1) printf("\n"); 82 else 83 printf("\n\n"); 84 } 85 } 86 return 0; 87 }
?
posted on 2013-03-14 21:01 symons 閱讀(...) 評論(...) 編輯 收藏
)
)
