1
#include<stdio.h>
2
#include<string.h>
3
int P[8][2]=
{
{-2,-1},
{-2,1},
{-1,-2},
{-1,2},
{1,-2},
{1,2},
{2,-1},
{2,1}};
4
struct C
{int r,l;};
5
C Q[30];
6
char use[30][30];
7
int p,q,K,ans,f;
8
void di(int a,int b)
9

{
10
if(K==ans)f=1;
11
if(f)return;
12
int i,r,l;
13
for(i=0;i<8;i++)
14
{
15
r=a+P[i][0];
16
l=b+P[i][1];
17
if(r>=1 && r<=p && l>=1 && l<=q && use[r][l])
18
{
19
K++;
20
use[r][l]=0;Q[K].l=l;Q[K].r=r;
21
//if(K==ans){f=1;return;}
22
di(r,l);
23
if(f)return;
24
use[r][l]=1;
25
K--;
26
}
27
}
28
29
}
30
int main()
31

{
32
int i,Kase,l;
33
scanf("%d",&Kase);
34
l=0;
35
while(l<Kase)
36
{
37
memset(use,1,sizeof(use));
38
memset(Q,0,sizeof(Q));
39
scanf("%d%d",&q,&p);
40
ans=p*q;
41
K=1;f=0;
42
Q[K].l=1;Q[K].r=1;
43
use[1][1]=0;
44
di(1,1);
45
printf("Scenario #%d:\n",++l);
46
if(!f)printf("impossible\n\n");
47
else
48
{
49
for(i=1;i<=ans;i++)printf("%c%c",Q[i].r+'A'-1,Q[i].l+'0');
50
printf("\n\n");
51
}
52
}
53
return 0;
54
55
}
56
深度优先搜索。
因为需要便利整个棋盘有要求遍历的顺序字典序最小。
那么可以确定深搜的顺序就是从A1开始的。
由于p*q<=26当期中一个为2的时候另一个大于10的时候肯定是不能遍历的。
所以不需要考虑B11 B9等一类出现时候字典序的问题了