自动搬运

查看原文

来自洛谷，原作者为

	Crazyouth 系统维护，该内容暂不可见。:)

搬运于2025-08-24 23:02:33，当前版本为作者最后更新于2024-08-24 19:44:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Sol. by "Cuazyoxi"

考虑两种搜索策略。

广搜

由于 cy（Cuazyoxi）需要尽量远离 hb（Happybob），所以每次 cy 一定会往远离 hb 的方向走，hb 同理。也就是说，易证最终两人路线一定满足 cy 远离 hb，hb 靠近 cy，但是正向搜索这样会 WA on #1，为什么呢？如果说 cy 远离 hb 就进入队列，那么 cy 遇到死胡同代码就挂了，因此需要枚举 cy 落点，再据此将每个 hb 能达到最小距离的点枚举下去。

但是这个代码会 WA on #5，原因是 hb 往离 cy 近的方向走不一定最优，因为 cy 可以和 hb 绕圈，这时候 hb 去堵截 cy 是最优的，怎么解决这种问题呢？见下。

深搜

记搜，$ans_{i,j,k,l}$ 表示把 cy 在 $(i,j)$，hb 在 $(k,l)$ 最多多少步抓到 cy，转移的时候枚举 cy 落点，据此搜索 hb 往哪个方向最快抓，再判断 cy 这一步是否明智。

但是这个代码会 WA on #2，原因是判断是否访问过的时候 $vis$ 数组妨碍了 hb 的走位，导致出现错误答案，如何避免？见下。

Mix it up!

如果在深搜的时候不记录 vis，而是搜索 hb 所有离 cy 近的路线，那不就过了？正确的。时空峰值：$8$ ms，$564$ KB。

Std.

#include <bits/stdc++.h>
using namespace std;
string s[20];
int dist[20][20],dy[5]={0,1,0,-1,0},dx[5]={-1,0,1,0,0},vis[20][20];
int vis2[20][20],ans[20][20][20][20];
int x[3],y[3],n,m;
void getdist(int nx,int ny)
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	dist[i][j]=1e9,vis2[i][j]=0;
	vis2[nx][ny]=1;
	dist[nx][ny]=0;
	queue<pair<int,int>> pos;
	queue<int> step;
	pos.push({nx,ny});
	step.push(0);
	while(pos.size())
	{
		int x=pos.front().first,y=pos.front().second,stp=step.front();
		pos.pop();
		step.pop();
		dist[x][y]=stp;
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>n||xx<1||yy>n||yy<1||vis2[xx][yy]||s[xx][yy]=='1') continue;
			vis2[xx][yy]=1;
			pos.push({xx,yy});
			step.push(stp+1);
		}
	}
}
int dfs(int xc,int yc,int xh,int yh)
{
	if(xc==xh&&yc==yh) return 0;
	if(ans[xc][yc][xh][yh]) return ans[xc][yc][xh][yh];
	int mintime=1e9,maxtime=0;
	for(int ii=0;ii<5;ii++)
	{
		int xxc=xc+dx[ii],yyc=yc+dy[ii];
		if(xxc<1||xxc>n||yyc<1||yyc>n||s[xxc][yyc]=='1') continue;
		getdist(xxc,yyc);
		mintime=1e9;
		vis[xxc][yyc]=1;
		int xxh,yyh,fxh,fyh,mindist=1e9,xxh2,yyh2,fxh2,fyh2,mindist3=1e9;
		for(int i=0;i<=4;i++)
		{
			xxh=dx[i]+xh;yyh=dy[i]+yh;
			if(xxh>n||xxh<1||yyh>n||yyh<1||s[xxh][yyh]=='1') continue;
			fxh=xxh;
			fyh=yyh;
			for(int j=0;j<=4;j++)
			{
				xxh2=dx[j]+fxh;yyh2=dy[j]+fyh;
				if(xxh2>n||xxh2<1||yyh2>n||yyh2<1||s[xxh2][yyh2]=='1') continue;
				if(dist[xxh2][yyh2]<=mindist)
				{
					mindist=dist[xxh2][yyh2];
					fxh2=xxh2;
					fyh2=yyh2;
				}
			}
		}
		int nxh2,nyh2;
		for(int i=0;i<=4;i++)
		{
			nxh2=xh+dx[i],nyh2=yh+dy[i];
			if(nxh2>n||nxh2<1||nyh2>n||nyh2<1||s[nxh2][nyh2]=='1') continue;
			for(int j=0;j<=4;j++)
			{
				int nxh3=nxh2,nyh3=nyh2;
				nxh3+=dx[j],nyh3+=dy[j];
				if(nxh3>n||nxh3<1||nyh3>n||nyh3<1||s[nxh3][nyh3]=='1') continue;
				if(dist[nxh3][nyh3]==mindist)
				{
					mintime=min(mintime,dfs(xxc,yyc,nxh3,nyh3)+1);
				}
			}
		}
		if(mintime==1e9) mintime=0;
		maxtime=max(maxtime,mintime);
	}
	ans[xc][yc][xh][yh]=maxtime;
	return maxtime;
}
int main()
{
	cin>>n;
	cin>>x[1]>>y[1]>>x[2]>>y[2];
	for(int i=1;i<=n;i++)
	cin>>s[i],s[i]=' '+s[i];
	getdist(x[1],y[1]);
	if(dist[x[2]][y[2]]==1e9)
	{
		cout<<"inf";
		return 0;
	}
	cout<<dfs(x[1],y[1],x[2],y[2]);
	return 0;
}