转载请注明出处：http://blog.csdn.net/u012860063?viewmode=contents

题目链接：http://poj.org/problem?

id=2488

----------------------------------------------------------------------------------------------------------------------------------------------------------

欢迎光临天资小屋：http://user.qzone.qq.com/593830943/main

----------------------------------------------------------------------------------------------------------------------------------------------------------

Description

Background 

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey 

around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board,
but it is still rectangular. Can you help this adventurous knight to make travel plans? 



Problem 

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

Output

Sample Input

3

1 1

2 3

4 3

Sample Output

Scenario #1:

A1

Scenario #2:

impossible

Scenario #3:

A1B3C1A2B4C2A3B1C3A4B2C4

大致题意:

给出一个国际棋盘的大小，推断马是否能不反复的走过全部格，并记录下当中按字典序排列的第一种路径。

代码例如以下：

#include <cstdio>

#include <cstring>

#define M 26

struct node

{

	int x, y;

}w[M*M];

bool vis[M][M];

int p, q;

int flag = 0;

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

//按此顺序搜索出来的结果就是字典序

bool judge(int x, int y)

{

	if(x>=0&&x<q&&y>=0&&y<p&&!vis[x][y])

		return true;

	return false;

}

void dfs(int x, int y, int step)

{

	w[step].x = x,w[step].y = y;

	vis[x][y] = true;

	if(step == p*q-1)

	{

		flag = 1;

		return ;

	}

	for(int i = 0; i < 8; i++)

	{

		int dx = w[step].x+dir[i][0];

		int dy = w[step].y+dir[i][1];

		if(judge(dx,dy))

		{

			vis[dx][dy] = true;

			dfs(dx,dy,step+1);

			if(flag)//一但找到就退出搜索

				return;

			vis[dx][dy] = false;

		}

	}

	return ;

}

void print()

{

	for(int i = 0; i < p*q; i++)//列为字母，行为数字

	{

		printf("%c%d",w[i].x+'A',w[i].y+1);

	}

	printf("\n\n");

}

int main()

{

	int t, i, j, cas = 0;

	scanf("%d",&t);

		while(t--)

		{

			memset(vis,false,sizeof(vis));

			flag = 0;

			scanf("%d%d",&p,&q);

			for(i = 0; i < q; i++)//列

			{

				for(j = 0; j < p; j++)//行

				{

					dfs(i,j,0);

					if(flag)

						break;

				}

				if(flag)

					break;

			}

			printf("Scenario #%d:\n",++cas);

			if(flag)

				print();

			else

				printf("impossible\n\n");

		}

	return 0;

}