POJ 2488 A Knight's Journey

DFS+回溯，其实不用从所有节点开始搜索，因为要求输出的是字典序，所以只从A1开始搜索，能一次搜到便是存在，否则不存在。写完代码才意识到。另外注意字典序时，方向数组要写对。
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <stack>
  5 using namespace std;
  6 int c;
  7 int n,p,q;
  8 int start_x,start_y;
  9 int total_count=0;
 10 bool flag=false;
 11 bool visited[30][30]={false};
 12 typedef struct Node {
 13     int x,y;
 14 }Node;
 15 Node nodes[8]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
 16 typedef struct Father {
 17     int x,y;
 18 }Father;
 19 Father father[30][30]={{-1,-1}};
 20 void init()
 21 {
 22     flag=false;
 23     memset(visited,false,sizeof(visited));
 24 }
 25 bool check(int x,int y)
 26 {
 27     if(!(0<=x&&x<p&&0<=y&&y<q))    return false;
 28     return true;
 29 }    
 30 void out_result(int a,int b)
 31 {
 32     stack<int> S;
 33     int x=a,y=b;
 34     printf("Scenario #%d:\n",c);
 35     S.push(b);
 36     S.push(a);
 37     while(!(father[x][y].x==-1&&father[x][y].y==-1)) {
 38         S.push(father[x][y].y);
 39         S.push(father[x][y].x);
 40         int X=father[x][y].x,Y=father[x][y].y;
 41         x=X;
 42         y=Y;
 43     }
 44     while(!S.empty()) {
 45         putchar(S.top()+'A');
 46         S.pop();
 47         putchar(S.top()+'1');
 48         S.pop();
 49     }
 50     putchar('\n');
 51     putchar('\n');
 52 }
 53 void dfs(int x,int y,int count) 
 54 {
 55     if(flag)    return;
 56     if(count==total_count) {
 57         out_result(x,y);
 58         flag=true;
 59         return ;
 60     }
 61     int i;
 62     for(i=0;i<8;i++) {
 63         if(check(x+nodes[i].x,y+nodes[i].y)&&!visited[x+nodes[i].x][y+nodes[i].y]) {
 64             visited[x+nodes[i].x][y+nodes[i].y]=true;
 65             father[x+nodes[i].x][y+nodes[i].y].x=x;
 66             father[x+nodes[i].x][y+nodes[i].y].y=y;
 67             dfs(x+nodes[i].x,y+nodes[i].y,count+1);
 68             visited[x+nodes[i].x][y+nodes[i].y]=false;
 69         }
 70     }
 71 }
 72 int main()
 73 {
 74     scanf("%d",&n);
 75     for(c=1;c<=n;c++) {
 76     here:        scanf("%d%d",&q,&p);
 77         int i,j;
 78         total_count=p*q;
 79         for(i=0;i<p;i++) {
 80             for(j=0;j<q;j++) {
 81                 visited[i][j]=true;
 82                 father[i][j].x=-1;
 83                 father[i][j].y=-1;
 84                 start_x=i;
 85                 start_y=j;
 86                 dfs(start_x,start_y,1);
 87                 if(flag) {
 88                     init();
 89                     c++;
 90                     if(c<=n)
 91                         goto here;
 92                     else return 0;
 93                 }
 94                 init();
 95             }
 96         }
 97         if(!flag) {
 98             printf("Scenario #%d:\n",c);
 99             printf("impossible\n");
100             putchar('\n');
101         }
102     }
103     return 0;
104 }