2015-06-05

问题简述：

　　有一个 p*q 的棋盘，一个骑士（就是中国象棋里的马）想要走完所有的格子，棋盘横向是 A...Z（其中A开始 p 个），纵向是 1...q。

　　原题链接：

解题思路：

　　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 
     
       9 #include 
      
       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