TOJ 1702.A Knight's Journey，toj1702.a

TOJ 1702.A Knight's Journey，toj1702.a

2015-06-05

問題簡述：

　　有一個 p*q 的棋盤，一個騎士（就是中國象棋裡的馬）想要走完所有的格子，棋盤橫向是 A...Z（其中A開始 p 個），縱向是 1...q。

　　原題鏈接：http://acm.tju.edu.cn/toj/showp1702.html

解題思路：

　　DFS：深搜把所有情況都考慮一遍，當騎士走出棋盤或走到原來走過的格子時，旅行失敗了；當騎士能一直走下去直到走過的格子數等於 p*q 時，旅行成功。

　　提交過程中一直有一個問題使這個代碼一直WA，最後才發現是 p、q輸入反了，先輸入的數是 q（也就是縱向的數字標號）。。。

源代碼：

 1 /*
 2 OJ: TOJ
 3 ID: 3013216109
 4 TASK: 1702.A Knight's Journey
 5 LANG: C++
 6 NOTE: DFS
 7 */
 8 #include <cstdio>
 9 #include <cstring>
10 
11 int n,p,q,flag;
12 int x[8]={-2,-2,-1,-1,1,1,2,2};
13 int y[8]={-1,1,-2,2,-2,2,-1,1};
14 char tmp[27]={"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
15 char ans1[27];
16 int ans2[27];
17 int visited[35][35];
18 
19 bool dfs(int a,int b) {
20     if(!visited[a][b]) visited[a][b]=1;
21     else return false;　　　　  //如果走到已經走過的棋盤，則失敗
22     ans1[flag]=tmp[a-1];
23     ans2[flag]=b;
24     flag++;
25     if(flag>=p*q) return true; //走完所有的格子，則成功
26     for(int i=0;i<8;i++) {
27         if(a+x[i]>0&&a+x[i]<=p&&b+y[i]>0&&b+y[i]<=q&&dfs(a+x[i],b+y[i]))
28             return true;　　　　//如果下一步不走出棋盤且能走完剩下的格子，則成功
29     }
30     visited[a][b]=0;
31     flag--;　　　　　　　　　　　 //回溯
32     return false;　　　　　　　　//不能成功的走完所有的格子，則失敗
33 }
34 
35 int main()
36 {
37     scanf("%d",&n);
38     int i,j,k=1;
39     while(n--) {
40         printf("Scenario #%d:\n",k++);
41         scanf("%d %d",&q,&p);
42         flag=0;
43         memset(visited,0,sizeof(visited));
44         int solved=0;
45         for(i=1;i<=p;i++) {
46             for(j=1;j<=q;j++) { //遍歷所有可能的起點
47                 if(dfs(i,j)) {
48                     solved=1;
49                     for(int l=0;l<p*q;l++)
50                         printf("%c%d",ans1[l],ans2[l]);
51                     printf("\n\n");
52                 break;
53                 }
54             }
55         }
56         if(!solved)
57             printf("impossible\n\n");
58     }
59     return 0;
60 }