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}};
4struct C{int r,l;};
5C Q[30];
6char use[30][30];
7int p,q,K,ans,f;
8void 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
}
30int 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
深度優(yōu)先搜索。
因?yàn)樾枰憷麄€(gè)棋盤有要求遍歷的順序字典序最小。
那么可以確定深搜的順序就是從A1開始的。
由于p*q<=26當(dāng)期中一個(gè)為2的時(shí)候另一個(gè)大于10的時(shí)候肯定是不能遍歷的。
所以不需要考慮B11 B9等一類出現(xiàn)時(shí)候字典序的問題了