自动搬运

查看原文

来自洛谷，原作者为

	zhuweiqi 攀峰之高险，岂有崖颠；搏海之明辉，何来彼岸？前进不止，奋斗不息。

搬运于2025-08-24 22:52:29，当前版本为作者最后更新于2023-11-14 20:10:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意：给你一个迷宫，其中每个格子可能会有移动方式的限制，求从左上角走到右下角的最少步数。

思路：首先，我们需要排除起点或终点为 * 的情况，此时显然无解，输出 $-1$。否则，对全图进行一遍 bfs，记 $f_{i,j}$ 为从 $(1,1)$ 走到 $(i,j)$ 的最少步数，初始时需要将 $f$ 数组全部赋值为 $-1$，其中对于当前格子（设为 $(x,y)$）的扩展，需要分类讨论，如果 $a_{x,y}$ 为 *，则不能进行扩展；如果 $a_{x,y}$ 为 |，则只能上下扩展，即只能走到横坐标为 $x\pm1$ 且纵坐标为 $y$ 的格子（前提是这些格子在边界范围之内且尚未被扩展过，下同）；如果 $a_{x,y}$ 为 -，则只能左右扩展，即只能走到横坐标为 $x$ 且纵坐标为 $y\pm1$ 的格子；如果 $a_{x,y}$ 为 +，则上下左右都可以扩展，即可以走到横坐标为 $x\pm1$ 且纵坐标为 $y\pm1$ 的格子。最终，答案即为 $f_{n,m}$ 的值，特别地，由于题目中说道：初始时在左上角和在右上角结束时都算 $1$ 步，故我们需要将 $f_{1,1}$ 的初始值赋值为 $1$。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[22][22];
int f[22][22];
queue<pair<int,int>> q;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool bj(int x,int y){return x>=1 && x<=n && y>=1 && y<=m;}
void bfs(){
	memset(f,-1,sizeof(f));
	f[1][1]=1;
	q.push({1,1});
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		int i,j;
		if(a[x][y]=='|') i=0,j=2;
		if(a[x][y]=='-') i=2,j=4;
		if(a[x][y]=='+') i=0,j=4;
		if(a[x][y]=='*') continue;
		for(;i<j;i++){
			int nx=x+dir[i][0];
			int ny=y+dir[i][1];
			if(bj(nx,ny) && f[nx][ny]==-1){
				f[nx][ny]=f[x][y]+1;
				q.push({nx,ny});
			}
		}
	}
	return;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
		if(a[1][1]=='*' || a[n][m]=='*'){
			printf("-1\n");
			continue;
		}
		bfs();
		printf("%d\n",f[n][m]);
	}
	return 0;
}