TOJ 1702.A Knight's Journey

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 }