题目链接：

题目解读：首先得弄清楚国际象棋中关于“马走日”的规则，如上图中的马，它的下一步的走法有8中，所以对每一个位置的马，它所能走的8个方向坐标设置为

dir[8][2]= {

{

-1,-2},{

1,-2},{

-2,-1},{

2,-1},{

-2,1},{

2,1},{

-1,2},{

1,2}};

对于最后一组测试案例4 3

画出图解如下：

解题代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 int vis[100][100]; 7 int p,q,flag; 8 int dir[8][2]= {
   {-1,-2},{
   1,-2},{-2,-1},{
   2,-1},{-2,1},{
   2,1},{-1,2},{
   1,2}}; 9 struct node{10     int x,y;11 }a[100];12 void dfs(int x,int y,int step)13 {14     a[step].x=x; a[step].y=y;15     if(step==p*q){16         for(int i=1;i<=step;i++)17             printf("%c%d",a[i].y-1+'A',a[i].x);18         printf("\n");19         flag=1;20     }21     if(flag) return;22     for(int i=0;i<8;i++){23         int xx=x+dir[i][0];24         int yy=y+dir[i][1];25         if(xx>0&&xx<=p &&yy>0&&yy<=q && vis[xx][yy]==0){26             vis[xx][yy]=1;27             dfs(xx,yy,step+1);28             vis[xx][yy]=0;29         }30     }31 }32 int main()33 {34     int T,cnt=1;scanf("%d",&T);35     while(T--){36         flag=0;37         memset(vis,0,sizeof(vis));38         scanf("%d%d",&p,&q);39         printf("Scenario #%d:\n",cnt++);40         vis[1][1]=1;41         dfs(1,1,1);42         if(flag==0)43             printf("impossible\n");44         printf("\n");45     }46     return 0;47 }