很久很久以前就见过的，当时不会做，最近在搞DFS，做做吧。。。花时间好长，折腾了一下午，由于一个1打成了0，2Y。。。期间可耻的冲进DISCUSS查错，有时候DISCUSS也会误导人啊，里面说啥的也有，很多不靠谱的说法。。。还好，自己又检查了一遍代码，发现这个错误。。。把深搜的过程写复杂了，看discuss的时候看见有简单的表达方式。
由于把代码打出来后，发现行和列倒过来了，改一下输入就好。我把英文看做行，数字看做列，所以字典序应该是先上 再左。所以深搜的时候按这个顺序。每组数据注意多输出个空行。
1 #include2 #include 3 int p[27][27],m,q,z; 4 int judge() 5 { 6 int i,j; 7 for(i = 1;i <= m;i ++) 8 for(j = 1;j <= q;j ++) 9 {10 if(p[i][j] == 0)11 return 0;12 }13 return 1;14 }15 void dfs(int x,int y,int step)16 {17 int i,j,k;18 char o;19 p[x][y] = step;20 if(z) return ;21 if(judge())22 {23 z = 1;24 for(i = 1; i <= m*q;i ++)25 {26 for(j = 1;j <= m;j ++)27 for(k = 1;k <= q;k ++)28 {29 if(p[j][k] == i)30 printf("%c%d",'A'+j-1,k);31 }32 }33 printf("\n");34 }35 if(p[x-2][y-1] == 0 && x-2 >= 1 && y-1 >= 1)36 {37 dfs(x-2,y-1,step+1);38 p[x-2][y-1] = 0;39 }40 if(p[x-2][y+1] == 0 && x-2 >= 1 && y+1 <= q)41 {42 dfs(x-2,y+1,step+1);43 p[x-2][y+1] = 0;44 }45 if(p[x-1][y-2] == 0&& x-1 >= 1 && y-2 >= 1)46 {47 dfs(x-1,y-2,step+1);48 p[x-1][y-2] = 0;49 }50 if(p[x-1][y+2] == 0&& x-1 >= 1 && y+2 <= q)51 {52 dfs(x-1,y+2,step+1);53 p[x-1][y+2] = 0;54 }55 if(p[x+1][y-2] == 0&& x+1 <= m && y-2 >= 1)56 {57 dfs(x+1,y-2,step+1);58 p[x+1][y-2] = 0;59 }60 if(p[x+1][y+2] == 0&& x+1 <= m && y+2 <= q)61 {62 dfs(x+1,y+2,step+1);63 p[x+1][y+2] = 0;64 }65 if(p[x+2][y-1] == 0 && x+2 <= m && y-1 >= 1)66 {67 dfs(x+2,y-1,step+1);68 p[x+2][y-1] = 0;69 }70 if(p[x+2][y+1] == 0 && x+2 <= m && y+1 <= q)71 {72 dfs(x+2,y+1,step+1);73 p[x+2][y+1] = 0;74 }75 return ;76 }77 int main()78 {79 int t,i,j,k,num = 1;80 scanf("%d",&t);81 while(t--)82 {83 z = 0;84 scanf("%d%d",&q,&m);85 printf("Scenario #%d:\n",num);86 dfs(1,1,1);87 if(!z)88 printf("impossible\n");89 printf("\n");90 num ++;91 }92 return 0;93 }