Description
整天待在方块里的骑士感到特别的无聊，于是他决定来一场说走就走的旅行。
然而他只能走日字，如右图所示，如果骑士当前在棋盘的正中央，他可以走标记有白点的八个区域。
骑士知道世界是一个列数和行数均不超过8（即8×8）的棋盘。
并且骑士有一点强迫症，如果用A-Z来表示列，1-99来表示横行，他只愿意走字典序最小的一条道路。
你能帮助勇敢的骑士制定一个适合他的旅行计划，使得他可以走遍整个棋盘吗？骑士可以在任一方块出发或者结束。
Input
第一行中有一个正整数n，代表数据有n组。
对于每组数据，都含有两个正整数p和q(1 <= p * q <= 26)，代表棋盘有p行q列。
Output
每组数据首先应当输出”Scenario #i:”，i代表输出的是第i组数据的结果。
然后在一行之内输出一条可以走遍棋盘的路径，如果有多条路径可以走遍棋盘，那么输出按字典序排序第一的路径。
最后，留一个空行。若现在是最后一条数据，则不留空行。
在输出路径时，用A代表第一列，B代表第二列..以此类推。而使用1代表第一行，2代表第二行。
例如，若要表示从第一行第一列到第二行第三列，可以用字符串：A1C3来表示。
Sample Input
样例输入①：
3
1 1
2 3
4 3
样例输入②：
4
5 5
3 3
4 5
6 3
Sample Output
样例输出①：
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
样例输出②：
Scenario #1:
A1B3A5C4A3B1D2E4C5A4B2D1C3B5D4E2C1A2B4D5E3C2E1D3E5
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4
Scenario #4:
impossible
#include<stdio.h>
#include<string.h>
int book[10][10];
int arr[8][2={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};//八个方向，根据途中马的位置，因为是字典序，所以它必须先走左上角，所以这八个方向左边优先
int a,b;
int res[100][2];//用来存xy是第几步走的
int found;//找到一个可以执行通道的标志
void dfs(int n,int m,int depth);
int main()
{
int n;
scanf("%d",&n);
int count=0;
int i,j;
while(n--)
{
memset(book,0,sizeof(book));
found=0;
count++;
scanf("%d %d",&a,&b);
printf("Scenario #%d:\n",count);
book[0][0]=1;
dfs(0,0,1);
if (!found)
printf("impossible\n");
if (n!=0)
putchar('\n');
}
}
void dfs(int n,int m,int depth)
{
res[depth][0]=m;//x坐标
res[depth][1]=n;//y坐标
if(depth==a*b)
{
found=1;
for(int i=1;i<=a*b;i++)
{
printf("%c%d",res[i][1]+'A',res[i][0]+1);
}
putchar('\n');
return;
}
int k;
int tx,ty;
for(k=0;k<8;k++)//八个方向
{
tx=m+arr[k][0];
ty=n+arr[k][1];
if(tx<0||tx>=a||ty<0||ty>=b)//临界处理
continue;
if(book[tx][ty]!=0)
continue;
if(found)
break;
book[tx][ty]=1;
dfs(ty,tx,depth+1);
book[tx][ty]=0;
}
}