自动搬运

查看原文

来自洛谷，原作者为

	iiiiiiiiiiiiiiiiiii ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

搬运于2025-08-24 22:00:13，当前版本为作者最后更新于2023-03-04 16:12:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道最短路的变形题。

首先，把传送的过程拆开，就是先射两枪，再走到一个传送门，传送到另一个传送门，共花费 $1$ 单位时间。

所以一共有两种走法：一种是走到相邻的格子（spfa 即可），一种是传送。

对于传送，在搜索时枚举起点传送门和终点传送门。在 spfa 之前 $O(n^2)$ 递推预处理出每个点向四个方向直线走最近的墙的距离，走到起点传送门即可。当然，传送到每个位置有 $3$ 种方案（起点传送门和终点传送门方向不同），但是起到的效果是一样的，需要取最小值。

注意：不一定是要挨着墙才能传送，会 $78$ 分。

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,sx,sy,tx,ty,vis[N][N],dis[N][N],b[N][N][4];
char ch[N][N];
struct node
{
	int x,y;
};
void bfs()
{
	memset(dis,0x3f,sizeof dis),dis[sx][sy]=0;
	queue<node> q;q.push({sx,sy}),vis[sx][sy]=1;
	while(!q.empty())
	{
		node f=q.front();q.pop(),vis[f.x][f.y]=0;
		for(int i=0;i<4;i++)//走到相邻格子
		{
			int nx=f.x+dx[i],ny=f.y+dy[i];
			if(ch[nx][ny]!='#'&&dis[f.x][f.y]+1<dis[nx][ny])
			{
				dis[nx][ny]=dis[f.x][f.y]+1;
				if(!vis[nx][ny])
					q.push({nx,ny}),vis[nx][ny]=1;
			}
		}
		for(int i=0;i<4;i++)//传送，枚举终点
		{
			int d=b[f.x][f.y][i],minn=INF,nx=f.x+dx[i]*d,ny=f.y+dy[i]*d;
			for(int j=0;j<4;j++)//枚举起点
				if(i!=j)
					minn=min(minn,b[f.x][f.y][j]);//取最小值转移
			minn+=dis[f.x][f.y]+1;
			if(dis[nx][ny]>minn)
			{
				dis[nx][ny]=minn;
				if(!vis[nx][ny])
					vis[nx][ny]=1,q.push({nx,ny});
			}
		}
	}
}
void solve()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>ch[i][j];
			if(ch[i][j]=='C')
				sx=i,sy=j;
			if(ch[i][j]=='F')
				tx=i,ty=j;
		}
	for(int i=1;i<=n;i++)//预处理墙壁距离
		for(int j=m;j;j--)
			if(ch[i][j]=='#')
				b[i][j][0]=-1;
			else
				b[i][j][0]=b[i][j+1][0]+1;
	for(int j=1;j<=m;j++)
		for(int i=n;i;i--)
			if(ch[i][j]=='#')
				b[i][j][1]=-1;
			else
				b[i][j][1]=b[i+1][j][1]+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ch[i][j]=='#')
				b[i][j][2]=-1;
			else
				b[i][j][2]=b[i][j-1][2]+1;
	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)
			if(ch[i][j]=='#')
				b[i][j][3]=-1;
			else
				b[i][j][3]=b[i-1][j][3]+1;
	bfs();
	if(dis[tx][ty]==INF)
		puts("nemoguce");
	else
		write(dis[tx][ty],"");
}