自动搬运

查看原文

来自洛谷，原作者为

	基地A_I 现实和理想之间，不变的是跋涉，暗淡与辉煌之间，不变的是开拓。

搬运于2025-08-24 21:53:25，当前版本为作者最后更新于2019-07-02 12:48:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

本来想刷DP题刷到了这个（为什么标签里面有动态规划？），权当复习一下Bfs吧。

前面的dalao吊打我，我的代码比较繁琐emm。

题解

熟练Bfs的同学应该不要多讲吧，思路简单

$\text{Bfs前准备}$

定义状态 Node

xG,yG,xM,yM,step; //表示G与M的位置,移动步数，看成一个整体

自然就有了四维的vis数组 $vis[xG][yG][xM][yM]$，来表示这个状态是否经历过。

$\text{Bfs}$

• 上下一起走

• 往左 G右 M左　；　往右　G左 M右 (有点绕)

• 注意：撞墙‘#’回来，蜘蛛网‘X’不可以走 (不懂可以看一下游戏视频)

• 处理好这几点，你就可以A了这题。

后记

关于游戏视频 ---> bilibili传送门 （这个游戏看起来还蛮好玩）

祝你AC （其实这道题不是很水qwq）

$\texttt{Code}$

#include<iostream>
#include<cstdio>
#include<queue>
#define N 37
using namespace std;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};
int n,m,XG,YG,XM,YM,ans=-1;
char map[N][N];
bool vis[N][N][N][N];
struct Node {
	int xG,yG;
	int xM,yM;
	int step;
};
queue<Node> q;
//	修改操作 （入队列，标记） 
inline void update(int x1,int y1,int x2,int y2,int step) {
	q.push((Node){x1,y1,x2,y2,step});
	vis[x1][y1][x2][y2] = 1;
}
//	判断是否能走 
inline bool check(int x1,int y1,int x2,int y2) {
	if(x1>=1&&x1<=n&&y1>=1&&y1<=m && x2>=1&&x2<=n&&y2>=1&&y2<=m)
		if(map[x1][y1]!='X' && map[x2][y2]!='X' && !vis[x1][y1][x2][y2])
			return 1;
	return 0;
}
//	判断是否到终点 
inline bool result(int x1,int y1,int x2,int y2) {
	if(map[x1][y1]=='T' && map[x2][y2]=='T')
		return 1;
	return 0;
}
//	一次操作 
inline bool work(int nx1,int ny1,int nx2,int ny2,int step)
{
	if(result(nx1,ny1,nx2,ny2))  {
		ans = step + 1;
			return 1;
		}
	if(check(nx1,ny1,nx2,ny2))	
		update(nx1,ny1,nx2,ny2,step+1);
	return 0;
}
void Bfs()
{
	update(XG,YG,XM,YM,0);
	while(!q.empty())
	{
		Node now = q.front(); q.pop();
//		printf("OK  ");
//		printf("xG=%d,yG=%d  xM=%d,yM=%d ,step=%d\n",now.xG,now.yG,now.xM,now.yM,now.step);
		for(int i=0;i<2;++i)
		{
			int nx1 = now.xG + dx[i] ,ny1 = now.yG + dy[i];
			int nx2 = now.xM + dx[i] ,ny2 = now.yM + dy[i];
		if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;	//挡住不走 
		if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
			if(work(nx1,ny1,nx2,ny2,now.step)) return ;
		}
		int nx1,ny1,nx2,ny2;
//		往右走 G左，M右 
		nx1 = now.xG + dx[2] ,ny1 = now.yG + dy[2];
		nx2 = now.xM + dx[3] ,ny2 = now.yM + dy[3];
		if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;	//挡住不走 
		if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
		if(work(nx1,ny1,nx2,ny2,now.step)) return ;
//		往左走 G右，M左 
		nx1 = now.xG + dx[3] ,ny1 = now.yG + dy[3];
		nx2 = now.xM + dx[2] ,ny2 = now.yM + dy[2];
		if(map[nx1][ny1] == '#') nx1=now.xG ,ny1=now.yG;	//挡住不走 
		if(map[nx2][ny2] == '#') nx2=now.xM ,ny2=now.yM;
		if(work(nx1,ny1,nx2,ny2,now.step)) return ;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			cin >> map[i][j];
			if(map[i][j] == 'G') XG=i ,YG=j;
			if(map[i][j] == 'M') XM=i ,YM=j; 
		}
	Bfs();
	if(ans == -1) printf("no\n");
	else printf("%d\n",ans);
	return 0; 
}