4780657_ac_16ms_292k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int n,l;
int mn[8]={-1,1,-2,2,-2,2,-1,1};
int ml[8]={-2,-2,-1,-1,1,1,2,2};
bool used[28][28];
int next[28][28];
bool done;
void testout()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=l;j++)
			cout<<next[i][j]<<" ";
		cout<<endl;
	}
}
bool dfs(int x,int y,int step)
{
	if(step==n*l) 
	{
		done=true;
		x=1,y=1;
		int k;
		while(next[x][y]!=-1)
		{
			cout<<char(y+'A'-1)<<x;
			k=next[x][y];
			x+=mn[k];
			y+=ml[k];
		}
		cout<<char(y+'A'-1)<<x;
		cout<<endl;
		return true;
	}
	for(int i=0;i<8;i++)
	{
		int tx=x+mn[i];
		int ty=y+ml[i];
		if(tx>=1 && tx<=n && ty>=1 && ty<=l )
		{
			if(used[tx][ty]==false)
			{
				used[tx][ty]=true;
				next[x][y]=i;
				if(dfs(tx,ty,step+1)) return true;
				used[tx][ty]=false;
				next[x][y]=-1;
			}
		}
	}
	return false;
}
int main()
{
	int testnumber;
	cin>>testnumber;
	for(int i=1;i<=testnumber;i++)
	{
		cin>>n>>l;
		memset(used,false,sizeof(used));
		memset(next,-1,sizeof(next));
		done=false;
		printf("Scenario #%d:\n",i);
		used[1][1]=true;
		dfs(1,1,1);
		if(!done) printf("impossible\n");
		cout<<endl;
	}
	return 0;
}