自动搬运

查看原文

来自洛谷，原作者为

	zhzkiller 私はまひろちゃん大好き！

搬运于2025-08-24 22:45:29，当前版本为作者最后更新于2023-07-12 18:00:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题外话

我本人写题解本来不写这个。

它不是紫题，为什么也要卡我 3 个小时！！！

题目描述

这道题要求我们求出一个最大的等待时间，使得小熊 Mecho 能够及时回到家里而不被蜜蜂堵住去路。

解题思路（正解）

很容易看出来这是一道广搜题，再一看就能看出来这是经典的双向 bfs 算法，而且本题答案具有单调性（更小的答案一定满足，更大的答案一定不满足）。我们只需每次二分答案后进行合法检查，具体表现为让小熊先搜 $S$ 步后让蜜蜂也搜 $1$ 步，看小熊是否能在 bfs 结束前到达终点即可。

请注意 此题解不是上述算法。

如果想练习双向 bfs 请移步它处。

解题思路（本人解法）

还是广搜和二分答案不变，我的做法是将蜜蜂所经过的路径打上类似时间戳的标记，在每次合法检查时仅对小熊进行移动，并实时与标记数组进行比较。该做法优点是比双向 bfs 好想，也好实现，缺点是有过多很细的细节需要注意，修死我了。

这个题解主要作用在于补充做题思路和服务想 AC 本题但是没有系统学习过双向 bfs 的同学。如果你没有更好的算法，那就和我一起坐牢吧~

完结撒花~

献上蒟蒻的 AC 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=810;

int n,k;
int stx,sty,edx,edy;
char a[N][N];
int dfn[N][N],d[N][N],cnt[N][N];
bool vis[N][N],v[N][N];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
queue< pair<int,int> > Q;

bool check(int t)
{
	memset(v,0,sizeof(v));
	Q.push({stx,sty});
	v[stx][sty]=true;d[stx][sty]=t==-1?0:t;
	while(Q.size())
	{
		int sx=Q.front().first,sy=Q.front().second;Q.pop();
		if(t==-1&&d[sx][sy]>dfn[sx][sy]) continue;
		if(sx==edx&&sy==edy)
		{
			while(Q.size()) Q.pop();
			return true;
		}
		int now=(d[sx][sy]-(t==-1?0:t))%k?(d[sx][sy]-(t==-1?0:t))/k+1:(d[sx][sy]-(t==-1?0:t))/k;
		for(int i=0;i<4;i++)
		{
			int tx=sx+dx[i],ty=sy+dy[i];
			if(tx&&ty&&tx<=n&&ty<=n&&!v[tx][ty]&&(a[tx][ty]=='G'||a[tx][ty]=='D')&&
			((t==-1?0:t)+now<dfn[tx][ty]-(k==1?k:0)||(t==-1?0:t)+now==dfn[tx][ty]
			-(k==1?k:0)&&cnt[sx][sy]!=(k-1?k-1:k))&&(now!=0||t+1<=dfn[tx][ty]))
			{
				if(cnt[sx][sy]==k&&t+now+1>dfn[tx][ty]) continue;
				v[tx][ty]=true;
				Q.push({tx,ty});
				if(t==-1)
				{
					cnt[tx][ty]=cnt[sx][sy]+1;
					if(cnt[tx][ty]==k+1)
					{
						d[tx][ty]=d[sx][sy]+1;
						cnt[tx][ty]=1;
					}
					else d[tx][ty]=d[sx][sy];
				}
				else d[tx][ty]=d[sx][sy]+1;
			}
		}
	}
	return false;
}

void bfs()
{
	dfn[edx][edy]=1e9;cnt[stx][sty]=k;
	while(Q.size())
	{
		int sx=Q.front().first,sy=Q.front().second;Q.pop();
		for(int i=0;i<4;i++)
		{
			int tx=sx+dx[i],ty=sy+dy[i];
			if(tx&&ty&&tx<=n&&ty<=n&&!vis[tx][ty]&&(a[tx][ty]=='G'||a[tx][ty]=='M'))
			{
				if(!dfn[tx][ty]) dfn[tx][ty]=dfn[sx][sy]+1;
				Q.push({tx,ty});vis[tx][ty]=true;
			}
		}
	}
}

int main()
{
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='H') Q.push({i,j}),vis[i][j]=true;
			else if(a[i][j]=='M') stx=i,sty=j;
			else if(a[i][j]=='D') edx=i,edy=j;
		}
	}
	
	bfs();
	
	if(!check(-1))
	{
		printf("-1");
		return 0;
	}
	
	int l=0,r=n*n;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(mid<dfn[stx][sty]&&check(mid)) l=mid;
		else r=mid-1;
	}
	printf("%d",l);
	return 0;
}

必要细节

1.多测必清空，队列要出完。

2.蜜蜂并不能占领小熊的家，即：

a[tx][ty]!='D';

3.二分注意上下界及如何取 mid 的问题。

此代码细节

1.mid<dfn[stx][sty] 时可以不进搜索直接二分，优化不少。

2.时刻记得保持 d[sx][sy]<=dfn[sx][sy]。

注：题解代码仅供参考，可自行二次缩减优化，但严禁抄袭。