Knight Moves

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

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.

BFS 版本

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <climits>

using namespace std;

const int MAX = 8;
const int dirx[MAX] = {-2,-2,2,2,-1,-1,1,1},diry[MAX] = {1,-1,-1,1,2,-2,-2,2};

typedef struct Point{
	int x,y;
}Point;

Point p;
int cstep[MAX][MAX],dx,dy;
queue<Point> que;

void init(){
	int i,j;

	for(i=0;i<MAX;++i){
		for(j=0;j<MAX;++j){
			cstep[i][j] = -1;
		}
	}

	while(!que.empty()){
		que.pop();
	}
}


int bfs(int x,int y){
	int i,tx,ty;
	p.x = x;
	p.y = y;
	cstep[x][y] = 0;
	que.push(p);
	while(!que.empty()){
		p = que.front();
		que.pop();
		x = p.x;
		y = p.y;
		if(x==dx && y==dy)break;
		for(i=0;i<MAX;++i){
			tx = x + dirx[i];
			ty = y + diry[i];
			if(tx<0 || ty<0 || tx>=MAX || ty>=MAX)continue;
			if(cstep[tx][ty]!=-1)continue;
			cstep[tx][ty] = cstep[x][y] + 1;
			p.x = tx;
			p.y = ty;
			que.push(p);
		}
	}
	return cstep[dx][dy];
}

int main(){
	//freopen("in.txt","r",stdin);
	char csx,csy,cdx,cdy;
	int sx,sy,minx;
	while(scanf("%c%c %c%c%*c",&csy,&csx,&cdy,&cdx)!=EOF){
		sx = csx-‘1‘;
		sy = csy-‘a‘;
		dx = cdx-‘1‘;
		dy = cdy-‘a‘;
		init();
		minx = bfs(sx,sy);
		printf("To get from %c%c to %c%c takes %d knight moves.\n",csy,csx,cdy,cdx,minx);
	}
    return 0;
}

DFS 版本

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>

const int MAX = 8;
const int dirx[MAX] = {-2,-2,2,2,-1,-1,1,1},diry[MAX] = {1,-1,-1,1,2,-2,-2,2};

int cstep[MAX][MAX],minx,dx,dy;

void init(){
	int i,j;

	for(i=0;i<MAX;++i){
		for(j=0;j<MAX;++j){
			cstep[i][j] = INT_MAX;
		}
	}
}

void dfs(int x,int y,int cnt){
	if(x<0 || y<0 || x>=MAX || y>=MAX)return;
	if(x==dx && y==dy){
		if(cnt<minx)minx = cnt;
		return;
	}
	//通过下面注释掉的main方法，运行处8*8棋盘，任意两个点最短距离的最大值为6
	//所以加上这个剪枝，不加这个剪枝就超时
	if(cnt>6)return;
	if(cnt>cstep[x][y])return;
	cstep[x][y] = cnt;

	int i,tx,ty;

	for(i=0;i<MAX;++i){
		tx = x + dirx[i];
		ty = y + diry[i];
		dfs(tx,ty,cnt+1);
	}

}

int main(){
	//freopen("in.txt","r",stdin);
	char csx,csy,cdx,cdy;
	int sx,sy;
	while(scanf("%c%c %c%c%*c",&csy,&csx,&cdy,&cdx)!=EOF){
		sx = csx-‘1‘;
		sy = csy-‘a‘;
		dx = cdx-‘1‘;
		dy = cdy-‘a‘;
		minx = INT_MAX;
		init();
		dfs(sx,sy,0);
		printf("To get from %c%c to %c%c takes %d knight moves.\n",csy,csx,cdy,cdx,minx);
	}
    return 0;
}



/*
int main(){
//	freopen("out.txt","w",stdout);
	int i,j,ans;
	dx = 0,dy = 0;
	ans = -1;
	for(i=0;i<8;++i){
		for(j=0;j<8;++j){
			minx = INT_MAX;
			init();
			dfs(i,j,0);
			printf("%d,",minx);
			if(minx>ans)ans = minx;
		}
	}
	printf("\n%d\n",ans);
	return 0;
}
*/

HDU 1372 Knight Moves （搜索 使用 dfs bfs两种实现）,布布扣,bubuko.com

HDU 1372 Knight Moves （搜索 使用 dfs bfs两种实现）

原文：http://blog.csdn.net/iaccepted/article/details/23748039