#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
	int x;
	int y;

	Node(int px=-1,int py=-1):x(px),y(py) {}
};

Node path[100];
int cnt;
bool vis[50][50];
int p,q;

bool InBound(int x,int y)
{
	return (x>=0&&x<p)&&(y>=0&&y<q);
}

int Move[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};


bool dfs(int row,int col)
{
	int i;
	Node temp;

	if(cnt==p*q)
	{
		for(i=0;i<p*q;i++)
			cout<<(char)(path[i].y+'A')<<path[i].x+1;
		cout<<endl;

		return true;
	}


	for(i=0;i<8;i++)
	{
		temp.x=row+Move[i][0];
		temp.y=col+Move[i][1];
		
		if(!InBound(temp.x,temp.y)||vis[temp.x][temp.y])
			continue;
		
		path[cnt].x=temp.x;
		path[cnt].y=temp.y;
		cnt++;
		vis[temp.x][temp.y]=true;
		if(dfs(temp.x,temp.y))
			return true;

		cnt--;
		vis[temp.x][temp.y]=false;
	}
	
	return false;
}

int main()
{
	int i2;
	int cases;
	
	cin>>cases;
	for(i2=1;i2<=cases;i2++)
	{
		cin>>p>>q;
		
		cout<<"Scenario #:"<<i2<<endl;

		memset(vis,false,sizeof(vis));
		
		cnt=1;
		vis[0][0]=true;
		path[0].x=0;
		path[0].y=0;
		if(!dfs(0,0))
			cout<<"impossible"<<endl;
		
		if(i2!=cases)
			cout<<endl;
	}

	return 0;
}

• Re:想死的心都有了，能不能有哪位大牛提点一下，到底我为什么WA (105) linbzh 2009-12-23 23:52:43