搜索算法II:国际象棋Knight

搜索算法II:国际象棋Knight

国际象棋中的Knight(骑士)在移动时,必须向一个方向移动两格同时再垂直移动一格,与中国象棋的“马”走法一样。只要棋盘尺寸大于3*4,骑士总能跳到任何指定的一格上。对于标准的8*8的国际象棋棋盘,我们可以使用BFS计算出骑真士从A格子到B格子所需要的最小步数:

https://vjudge.net/problem/OpenJ_Bailian-2243


#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 8

char isVisited[MAXN][MAXN];

int inRange(int x){
	return 0<=x && x<MAXN;
}

int inRange(int x,int y){
	return inRange(x) && inRange(y);
}

struct qNode{
	int x;int y;int level;
	qNode(){}
	qNode(int xx,int yy,int ll)
	{ x=xx;y=yy;level=ll;}
};

int solve(int startX, int startY, int endX, int endY){
	if (startX==endX && startY == endY)
	{
		return 0;
	}

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

	memset(isVisited,0,sizeof(isVisited));

	std::queue< qNode > q;
	qNode curr;
	
	q.push(qNode(startX,startY,1));
	int winFlag=0;
	while (q.size()>0 && winFlag==0){
		curr = q.front();
		q.pop();
		for (int i=0;i<8;i++){
			int dx = curr.x+dir[i][0];
			int dy = curr.y+dir[i][1];
			if (dx==endX && dy==endY){
				ret = curr.level;
				winFlag=1;
				break;
			}
			if (inRange(dx,dy) && isVisited[dx][dy]==0){
				isVisited[dx][dy]=1;
				q.push(qNode(dx,dy,curr.level+1));
			}
		}
	}
	return ret;
}

int main(void){
	char start[3],end[3];
	while (scanf("%s %s",start,end)!=EOF){
		int startX = start[0] - 'a';
		int startY = start[1] - '1';
		int endX = end[0] - 'a';
		int endY = end[1] - '1';
		printf("To get from %s to %s takes %d knight moves.\n",
			start,end,
			solve(startX,startY,endX,endY) );
	}
	return 0;
}


这是常规的BFS问题。接下来,我们将在国际象棋的棋盘上放3个Knight,计算目标是从棋盘上确定一个格子,使得三个骑士在这个格子上汇合所用的总步数最少。

直接的方法:定义一个step[i][x][y],表示第i名骑士跳到(x,y)位置所需最少步数。直接将step[i]全初始化为-1,表示从未有骑士走过,初始位置steps[i][x][y]=0,而当骑士从steps[i][x][y]跳向steps[i][x'][y']时,可以令 steps[i][x'][y']=steps[i][x][y]+1 。搜索方法如下:

memset(steps,-1,sizeof(steps));
const int dir[8][2] = {
	{-2, -1},{-2,  1},{-1, -2},{-1,  2},
	{ 1, -2},{ 1,  2},{ 2, -1},{ 2,  1},
};

for (int knight=0;knight<MAXKNIGHT;knight++){
	std::queue< std::pair<int,int> > q;
	int x=startX[knight],y=startY[knight];
	steps[knight][x][y] = 0;
	q.push( std::make_pair(x,y) );
	while (q.size()>0){
		auto p = q.front();
		q.pop();
		for (int i=0;i<8;i++){
			x=p.first + dir[i][0];
			y=p.second + dir[i][1];
			if (inRange(x,y) && steps[knight][x][y]==-1){
				steps[knight][x][y] = steps[knight][p.first][p.second]+1;
				q.push( std::make_pair(x,y));
			}
		}
	}
}

搜索完成之后,遍历整个棋盘,看看哪个格子使得三个骑士的移动距离之和最小:

int minVal = INF;
for (int i=0;i<MAXN;i++){
	for (int j=0;j<MAXN;j++){
		int knightsums = 0;
		for (int k=0;k<MAXKNIGHT;k++){
			knightsums+=steps[k][i][j];
		}
		minVal = std::min(minVal,knightsums);
	}
}
printf("%d\n",minVal);

这样虽然完成了这个任务,但仍有优化空间,因为对每个骑士都把整个棋盘走完一遍,最后判断还要再将整个棋盘走一遍,如何让骑士在移动的过程中就可能找到集合点呢。我们的BFS中可以同时移动骑士和方向,即移动一步就扩展24个状态(3个骑士*8个方向),这样只需要使用1个队列,不过判断状态会稍微复杂一些。这里将三个骑士的坐标用一个数字表示,定义一个函数move(idx,knight,dir)idx表示这三个骑士的状态,knight表示第几名骑士(取0,1,2),dir表示方向(取0到7),函数返回值为移动后骑士的状态(若是不合法的移动则返回idx)。

这种方法需要频繁的调用move(),如果move使用更巧妙的设计(例如直接将数字使用8进制,并利用位运算得出各位数)则效率会更高,下边这种设计方法的效率稍差一些,每次move都要做很多次乘除和取余。

int move(int idx,int knight,int dir)
{
	const int direction[8][2] = {
		{-2, -1},{-2,  1},{-1, -2},{-1,  2},
		{ 1, -2},{ 1,  2},{ 2, -1},{ 2,  1},
	};
	int a[6],i=0;
	for (i=0;i<6;i++){
		a[i] = idx%10;
		idx/=10;
	}
	if ( inRange(a[2*knight]+direction[dir][0]
			,a[2*knight+1]+direction[dir][1] )){
		a[2*knight] += direction[dir][0];
		a[2*knight+1] += direction[dir][1];
	}

	int ret = 0;
	for (i=5;i>=0;i--){
		ret = 10*ret + a[i];
	}
	return ret;
}

由于现在使用整数保存状态,如果开6位数的数组会比较浪费,这里使用set<int>保存状态是否被访问过。

int isComplete(int idx){
	int a[6],i=0;
	for (i=0;i<6;i++){
		a[i] = idx%10;
		idx/=10;
	};
	return a[0]==a[2] && a[0] == a[4] &&
		a[1] == a[3] && a[1] == a[5];
}

void solve(const char *k1,const char *k2,const char *k3){
	int idx = (((((k1[0]-'A')*10
		+(k1[1]-'1'))*10
		+(k2[0]-'A'))*10
		+(k2[1]-'1'))*10
		+(k3[0]-'A'))*10
		+(k3[1]-'1');

	if (isComplete(idx)){
		printf("0\n");
	} else {
		int winFlag =0;
		int ret =0;
		std::queue< std::pair<int,int> > q;
		std::set<int> s;
		q.push( std::make_pair(idx,0) );
		s.insert(idx);
		while (q.size()>0 && winFlag==0) {
			auto curr = q.front();
			q.pop();
			for (int k=0;k<3 && winFlag==0 ;k++){
				for (int step = 0;step<8 && winFlag==0;step++){
					int next = move(curr.first,k,step);
					if ( isComplete(next) ){
						ret = curr.second+1;
						winFlag = 1;
						break;
					}
					if (s.count(next)==0){
						q.push(std::make_pair(next,curr.second+1));
						s.insert(next);
					}
				}
			}
		}
		printf("%d\n",ret);
	}
	return ;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注