> #include <stdio.h>
> #include <string.h>
> #include <queue>
> using namespace std;
> int y[8]={-2,-2,-1,-1,1,1,2,2};
> int x[8]={-1,1,-2,2,-2,2,-1,1};
> int a[9][9]={0};//棋盘用于记录每个位置是否都被遍历过
> int path[26]={0};//记录路径的选择
> queue <int > q_queue;
> queue <int > p_queue;
> bool all_done(int p,int q);//判断是否全部遍历
> int main()
> {
> 	int n,p,q;//n cases
> 	int i,j,k;
> 	scanf("%d",&n);
> 	for(i=0;i<n;i++)
> 	{
> 		scanf("\n");
> 		scanf("%d%d",&p,&q);
> 		q_queue.push(q);
> 		p_queue.push(p);
> 	}
> 	for(i=n;i>0;i--)
> 	{
> 		q=q_queue.front();
> 		q_queue.pop();
> 		p=p_queue.front();
> 		p_queue.pop();
> 		memset(a,0,sizeof(a));
> 		memset(path,0,sizeof(path));
> 		int curr_x,curr_y;
> 		curr_x=1;//记录初始位置
> 		curr_y=1;
> 		a[curr_x][curr_y]=1;
> 	    for(j=1;j<p*q;j++)//对于p*q的表格要全遍历完成需行走p*q-1次
> 		{
> 			for(k=path[j];k<8;k++)//对于每一步行走的试探
> 			{ 
> 			   if(curr_x+x[k]<=p&&curr_y+y[k]<=q
> 				  &&curr_x+x[k]>=1&&curr_y+y[k]>=1
> 				  &&a[curr_x+x[k]][curr_y+y[k]]!=1)//判断是否超界
> 			   {
> 				   curr_x=curr_x+x[k];//未超界向下走一步	   
> 				   curr_y+=y[k];
> 				   path[j]=k;//记录当前所走路径
> 				   a[curr_x][curr_y]=1;//标记相应单元格
> 				   break;//跳过此步
> 			   }
> 			} 
> 			if(k==8)//此时证明已经无法继续走应该回退到上一步
> 			{
> 			    path[j]=0;//清空当前步
> 			    j=j-1;//回退一步
> 			    a[curr_x][curr_y]=0;//清空当前标记
> 			    curr_x-=x[path[j]];
> 				curr_y-=y[path[j]];
> 			    path[j]++;
> 			    j=j-1;
> 			}
> 			if(j<0)
> 			{
> 				break;
> 			}
> 		}
> 	    if(all_done(p,q))
> 		{
> 		    curr_x=1;
> 			curr_y=1;
> 			printf("Scenario #%d:\n",n-i+1);
> 			printf("%c%d",('A'+curr_x-1),curr_y);
> 			for(int k=1;k<p*q;k++)
> 			{
> 				curr_x=curr_x+x[path[k]];
> 				curr_y=curr_y+y[path[k]];
> 				printf("%c%d",('A'+curr_x-1),curr_y);
> 			}
> 			printf("\n");
> 		}
> 		else
> 		{
> 			printf("Scenario #%d:\n",n-i+1);
> 			printf("impossible\n");
> 		}	
> 	}
> 	return 0;
> }
> bool all_done(int p,int q)
> {
> 	int i,j;
> 	for(i=1;i<=p;i++)
> 	{
> 		for(j=1;j<=q;j++)
> 		{
> 			if(a[i][j]==0)
> 				return false;
> 		}
> 	}
> 	return true;
> }