#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;
}

• Re:本人菜鸟为啥一直WA我不知道为啥一直不是字典序呢 (2145) alphachuang 2011-11-18 19:58:52