自动搬运

查看原文

来自洛谷，原作者为

	ZBXAPCY 开启学术，改善码风。

搬运于2025-08-24 23:14:12，当前版本为作者最后更新于2025-06-08 14:59:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在做本题之前可以先做一下马的遍历，两题的有些地方比较相似，只需稍加改动。

首先我们把马和象的到所有的位置的所需最短步数都在遍历的过程中记录下来，再看看有没有它们都能到的点，如果有就说明在这个点它们中的一方有可能被吃掉，走到这个点所需的步数当然就是它们的步数之和了。

假设我们已经把马和象的可能到路径都搜索了一遍。取它们到可能互吃的点的步数的最小值。这个最小值就是我们要的答案啦！

以下是代码。

#include<bits/stdc++.h>
using namespace std;
int a[55][55],b[55][55],ans=99999999,n,mx,my,xx,xy;//a数组用于记录马到每个点的步数，b数组记录象，其实它们也起到了布尔作用，具体见代码。 
//n用于记录棋盘大小，注意棋盘的范围是0到n。mx,my,xx,xy用于记录马和象的初始位置。
//因为ans是要取最小值，所以先赋成很大的数。
void mbfs(){
	int t=1,h=0,x[]={1,1,-1,-1,2,2,-2,-2},o[3500][2]={mx,my},y[]={2,-2,2,-2,1,-1,1,-1};//o是队列，t是队列的头，h是尾。 
	while(h<t){//手打队列的标配 
		for(int i=0;i<8;i++){//遍历8个方向 
			int nx=o[h][0]+x[i],ny=o[h][1]+y[i];
			if(nx<0||ny<0||nx>n||ny>n||a[nx][ny]!=-1)
				continue;//如果超出棋盘范围或是已经走过了就跳过 
			o[t][0]=nx;o[t][1]=ny;//记录坐标 
			a[nx][ny]=a[o[h][0]][o[h][1]]+1;//步数=上一步的步数加一 
			t++;//尾端加一 
		}
		h++;//头加一 
	}
}
void xbfs(){
	int t=1,h=0,x[]={2,2,-2,-2},y[]={-2,2,-2,2},o[3500][2]={xx,xy};//与马的遍历差不多，这里就不说了 。 
	while(h<t){
		for(int i=0;i<4;i++){
			int nx=o[h][0]+x[i],ny=o[h][1]+y[i];
			if(nx<0||ny<0||nx>n||ny>n||b[nx][ny]!=-1)
				continue;
			o[t][0]=nx;o[t][1]=ny;
			b[nx][ny]=b[o[h][0]][o[h][1]]+1;
			t++;
		}
		h++;
	}
}
int main(){
	cin>>n>>my>>mx>>xy>>xx;
	if(mx==xx&&my==xy){cout<<0;return 0;} //特判，如果它们在同一位置则直接输出0 
	memset(a,-1,sizeof(a));
	memset(b,-1,sizeof(b));//先把数组全部赋值为-1,方便以后判断 
	a[mx][my]=b[xx][xy]=0;//到起点的位置都是0 
	mbfs();xbfs();//对马和象进行搜素 
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)//遍历每个点，具体做法之前已经说了 
		if(a[i][j]!=-1&&b[i][j]!=-1)//如果有一个点是-1就说明有一方没有到，就不能算是吃
			ans=min(ans,a[i][j]+b[i][j]);
	if(ans>99999998)cout<<-1;//注意如果它们不可能吃子则输出-1 
	else cout<<ans;
	return 0;
}

这是一篇异常粗糙的题解，根本原因还是我太菜了，呜呜呜。

看在这样的份上，能赏个赞吗？