POJ--2488 A Knight's Journeyb

题目链接：

注意两点：

1.本题要求按照字典序最小输出所以a[8]={-1, 1, -2, 2, -2, 2, -1, 1},b[8]={-2, -2, -1, -1, 1, 1, 2, 2}

2.由于 1 <= p * q <= 26所以printf("%c%d",que[i][1]-1+'A',que[i][0]);这样输出比较方便

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int n,m,t,sum,flag;
 6 int book[200][200],que[500][2];
 7 int dfs(int x,int y,int step)
 8 {
 9     int tx,ty;
10     int a[8]={-1, 1, -2, 2, -2, 2, -1, 1},b[8]={-2, -2, -1, -1, 1, 1, 2, 2};
11     que[step][0]=x;que[step][1]=y;
12     if(step==n*m)
13     {
14         flag=1;
15         return 0;
16     }
17     for(int i=0;i<8;i++)
18     {
19         tx=x+a[i];
20         ty=y+b[i];
21         if(tx<1||tx>n||ty<1||ty>m)
22         continue;
23         if(book[tx][ty]==0&&flag==0)
24         {
25             book[tx][ty]=1;
26             dfs(tx,ty,step+1);
27             book[tx][ty]=0;
28         }
29     }
30     return 0;
31 }
32 int main()
33 {
34     while(~scanf("%d",&t))
35     {
36         for(int k=1;k<=t;k++)
37         {
38             scanf("%d%d",&n,&m);
39             sum=n*m;
40             memset(book,0,sizeof(book));
41             memset(que,0,sizeof(que));
42             book[1][1]=1;
43             flag=0;
44             dfs(1,1,1);
45             printf("Scenario #%d:
",k);
46             if(flag==0)
47             printf("impossible
");
48             else
49             {
50                 for(int i=1;i<=n*m;i++)
51                 printf("%c%d",que[i][1]-1+'A',que[i][0]);
52                 printf("
");
53             }
54             if(k!=t)
55             printf("
");
56         }
57     }
58     return 0;
59 }

View Code