poj 2488 A Knight's Journey

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<stdio.h>
#include<string.h>
#define N 30
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
int mark[N][N],n,m,ff;
char ans[2*N],cur[N*2];
struct node
{
	int x,y;      //x记录横坐标，y记录纵坐标
}f[N];
int judge(int x,int y)
{
	if(x>0&&x<=n&&y>0&&y<=m)
		return 1;
	return 0;
}
void dfs(int x,int y,int num)
{
	int i,k,di,dj;
	if(num==n*m)      //找到答案后要立即记录路径
	{
		for(k=0;k<n*m;k++)
		{
			cur[2*k]=(char)f[k].x-1+‘A‘;    //把横纵坐标转换为字符型字母和数字
			cur[2*k+1]=(char)f[k].y+‘0‘;
		}
		cur[2*k]=‘\0‘;
		if(ff)
		{
			if(strcmp(cur,ans)<0)       //取字典序最小的序列
				strcpy(ans,cur);
		}
		else
		{
			ff=1;
			strcpy(ans,cur);
		}
		return ;
	}
	for(i=0;i<8;i++)
	{
		di=x+dx[i];
		dj=y+dy[i];
		if(judge(di,dj)&&!mark[di][dj])
		{
			mark[di][dj]=1;
			f[num].x=di;
			f[num].y=dj;
			dfs(di,dj,num+1);
			mark[di][dj]=0;  //回溯
		}
	}
	return ;
}
int main()
{
	int i,j,k,T,cnt=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++)     //字母在前
		{
			for(j=1;j<=m;j++)         //数字在后
			{
				memset(mark,0,sizeof(mark));
				mark[i][j]=1;
				f[0].x=i;
				f[0].y=j;
				ff=0;
				dfs(i,j,1);
				if(ff)   //搜到的第一个答案保证是字典序最小的
					break;
			}
			if(ff)
				break;
		}
		printf("Scenario #%d:\n",cnt++);
		if(!ff)
			printf("impossible\n\n");
		else
			printf("%s\n\n",ans);
	}
    
    return 0;
}

poj 2488 A Knight's Journey,布布扣,bubuko.com

poj 2488 A Knight's Journey

原文：http://blog.csdn.net/u011721440/article/details/23177961