1 #include<cstdio> 2 using namespace std; 3 const int b[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; 4 int a[30][30],p,q; 5 struct 6 { 7     int x,y; 8 }step[910]; 9 10 bool dfs(int x,int y,int now)11 {12     if (now==p*q) return true;13     for (int m=0;m<8;m++)14         {15             int dx=x+b[m][0];16             int dy=y+b[m][1];17             if (dx>=1 && dy>=1 && dx<=q && dy<=p && a[dx][dy]==0)18             {19                 a[dx][dy]=1;20                 step[now].x=dx;21                 step[now].y=dy;22                 if (dfs(dx,dy,now+1)) return true;23                 a[dx][dy]=0;24             }25         }26     return false;27 }28 29 int main()30 {31     int n;32     scanf("%d",&n);33     for (int t=1;t<=n;t++)34     {35         printf("Scenario #%d:\n",t);36         scanf("%d%d",&p,&q);37         for (int i=0;i<=26;i++)38             for(int j=0;j<=26;j++) a[i][j]=0;39         a[1][1]=1;40         step[0].x=1;41         step[0].y=1;42         if (!dfs(1,1,1)) printf("impossible\n\n");43         else44         {45             for (int i=0;i<p*q;i++) printf("%c%d",(char)step[i].x+‘A‘-1,step[i].y);46             printf("\n");47             printf("\n");48         }49     }50     return 0;51 }