Knight Moves acm入门 day1---bfs_dfs第五题

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once.
He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that,
once you have accomplished this, finding the tour would be easy.

Of course you know that it is vice versa. So you offer him to write a program that solves the ”difficult” part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input
The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a…h) representing the column and a digit (1…8) representing the row on the chessboard.

Output

For each test case, print one line saying ‘To get from xx to yy takes n knight moves.’.

骑士移动，其实骑士的移动也跟象棋的马一样，走“日”字步。
既然是求最短路径，当然是用bfs，当时没想到，用dfs写，一直跑不出答案，最后去百度了下发现其他人写dfs是加了一个限制条件，也就是当所用步数超过6时就返回，这样就不会跑不出来了。这应该也是国际象棋的一个规律把，也就是6步内能到任何位置。

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

一、dfs解法

#include <cstdio>
#include <cstring>
using namespace std;
int gra[10][10];
int s[2],e[2];
int stepx[8]={1,2,2,1,-1,-2,-2,-1};
int stepy[8]={2,1,-1,-2,-2,-1,1,2};
int res;
void dfs(int x,int y,int cnt)
{
	if(x==e[0]&&y==e[1]) {
		if(res>cnt) res=cnt;
		return ;
	}
	
	//这里如果设置一个超过6步返回的条件
	if(x>=8||x<0||y>=8||y<0||gra[x][y]||cnt>6) return ;//棋盘为8*8 
	
	
	for(int i=0;i<8;i++)
	{
		cnt++;
		gra[x][y]=1;
		dfs(x+stepx[i],y+stepy[i],cnt);	 
		cnt--;
		gra[x][y]=0;
	}
	
}
int main()
{
	char start[3],en[3];
	while(scanf("%s %s",start,en)!=EOF)
	{
		res=0x7fffffff;
		memset(gra,0,sizeof(gra));
		s[0]=start[0]-'a';
		s[1]=start[1]-'1';
		e[0]=en[0]-'a';
		e[1]=en[1]-'1';
		dfs(s[0],s[1],0);
		printf("To get from %s to %s takes %d knight moves.\n",start,en,res);
	}
}

同时，注意在输入起点和终点时建议使用输入字符串方式，这样就不需要处理缓冲区剩余的空格换行符，导致下一组数据输入时获取的字符为空格或换行符。

二、bfs解法

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int gra[10][10];
char start[3],en[3];
int s[2],e[2];
int stepx[8]={1,2,2,1,-1,-2,-2,-1};
int stepy[8]={2,1,-1,-2,-2,-1,1,2};
int pre[8][8][2];
int res;

int main()
{
	while(scanf("%s %s",start,en)!=EOF)
	{
		res=0x7fffffff;
		memset(gra,0,sizeof(gra));
		memset(pre,0,sizeof(pre));
		s[0]=start[0]-'a';
		s[1]=start[1]-'1';
		e[0]=en[0]-'a';
		e[1]=en[1]-'1';
		queue<int> q;
		q.push(s[0]);
		q.push(s[1]);
		int r=0;
		while(!q.empty())
		{
			int x1=q.front();
			q.pop();
			int y1=q.front();
			q.pop();
			if(x1==e[0]&&y1==e[1]) break;
			for(int i=0;i<8;i++)
			{
				int x2=x1+stepx[i],y2=y1+stepy[i];
				if(!gra[x2][y2]&&x2<8&&x2>=0&&y2<8&&y2>=0)
				{
					gra[x2][y2]=1;
					q.push(x2);
					q.push(y2);
					//记录路径当前位置的上一个点
					pre[x2][y2][0]=x1;
					pre[x2][y2][1]=y1;
				}
			}
		}
		int x3=e[0],y3=e[1];
		while(x3!=s[0]||y3!=s[1])
		{
			int px=pre[x3][y3][0],py=pre[x3][y3][1];
			x3=px;
			y3=py;
			r++;
		}
		printf("To get from %s to %s takes %d knight moves.\n",start,en,r);
	}
}