?

?

Description

Input

Output

Sample Input

3
1 1
2 3
4 3

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Source

?

题目链接：http://poj.org/problem?id=2488

?

题目大意：一个有n*m个格子的棋盘，模拟马走“日”字，求一个棋盘的所有格子能否被走完，如果能，求走的路径，即走格子的先后顺序，如果有多种情况，按字典序最小的情况。用横纵坐标表示格子位置，横坐标是字母，纵坐标是数字。

?

解题思路：DFS由第一个格子开始搜，因为每步只能走“日”字，所以每步有八个方向，因为按字典序最小的走，枚举方向时也按字典序。找到解的返回过程中标记路径。

?

代码如下：

?

#include 
  
   
#include 
   
     int dx[8]={-2,-2,-1,-1,1,1,2,2};//按字典序枚举8个方向 int dy[8]={-1,1,-2,2,-2,2,-1,1}; int xx[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}; char ansx[28]; //记录横坐标路径 int ansy[28]; //记录纵坐标路径 int sum,m,n,j; bool p; int a[28][28],vis[28][28]; void dfs(int x,int y,int cnt) { if(cnt==sum) //已走完所有格子 { ansx[j]=xx[x]; ansy[j++]=y+1; p=true; return; } for(int i=0;i<8;i++) { if(x+dx[i]<0||x+dx[i]>=n||y+dy[i]<0||y+dy[i]>=m) continue; if(vis[x+dx[i]][y+dy[i]]) continue; vis[x+dx[i]][y+dy[i]]=1; dfs(x+dx[i],y+dy[i],cnt+1); if(p) //若成功走完格子，往前标记每步路径 { ansx[j]=xx[x]; ansy[j++]=y+1; return; } vis[x+dx[i]][y+dy[i]]=0; } } int main() { int t; scanf(%d,&t); for(int cnt=1;cnt<=t;cnt++) { p=false,j=0; memset(vis,0,sizeof(vis)); vis[0][0]=1; scanf(%d%d,&m,&n); sum=n*m; dfs(0,0,1); printf(Scenario #%d: , cnt); if(!p) printf(impossible ); else //输出路径 { for(int i=j-1;i>=0;i--) printf(%c%d,ansx[i],ansy[i]); printf( ); } if(cnt
    
     
?
     
?