自动搬运

查看原文

来自洛谷，原作者为

	Jsxts_ [憨笑]

搬运于2025-08-24 22:34:07，当前版本为作者最后更新于2021-10-21 17:39:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

BFS 练手题。

一开始就把所有起始点都放进队列里面，注意用优先队列，从步数最少的开始扩展。

转移状态时，我们记录当前点的上一步往哪个方向走，并记录坐标和步数。对于脚下的点按题意扩展方向，查重时要加一维表示方向。特别注意，脚下是 $S$ 的时候可以向四方扩展，也不需要增加步数。

如果理解不了就看注释吧，也没啥好讲的。

代码：

#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9;
inline int read() {
	int s = 0,f = 1;char ch = getchar();
	while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
	while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
	return s*f;
}
int n,m,A,B,C,D,tot;
char a[2010][2010];
bool vis[2010][2010][4];//查重带方向 
//0左1右2上3下 
//0: x,y-1
//1: x,y+1
//2: x-1,y
//3: x+1,y
struct node {
	int x,y,step,dir;
	bool operator < (const node &a) const {
		return step > a.step;//优先找步数最少的 
	}
};
pair<int,int> aa[4000010];
int bfs() {
	priority_queue<node> q;
	for (int i = 1;i <= tot;i ++ )//所有起始点 
	q.push({aa[i].first,aa[i].second,0,0});
	while (!q.empty()) {
		node t = q.top();q.pop();
		int x = t.x,y = t.y,d = t.dir,s = t.step;
		if (x < 1 || y < 1 || x > n || y > m) continue;
		if (a[x][y] == 'E') return s;//找到直接返回 
		if (vis[x][y][d]) continue;//查重 
		if (a[x][y] == '#') continue;
		if (a[x][y] == '|') {//按题意转移，画画图就理解了 
			if (d == 0 || d == 1) q.push({x-1,y,s+A,2}), q.push({x+1,y,s+A,3});
			if (d == 2) q.push({x-1,y,s+A,2});
			if (d == 3) q.push({x+1,y,s+A,3});
		}
		if (a[x][y] == '-') {
			if (d == 2 || d == 3) q.push({x,y-1,s+A,0}), q.push({x,y+1,s+A,1});
			if (d == 0) q.push({x,y-1,s+A,0});
			if (d == 1) q.push({x,y+1,s+A,1});
		}
		if (a[x][y] == '/') {
			if (d == 0) q.push({x+1,y,s+B,3});
			if (d == 1) q.push({x-1,y,s+B,2});
			if (d == 2) q.push({x,y+1,s+B,1});
			if (d == 3) q.push({x,y-1,s+B,0});
		}
		if (a[x][y] == '\\') {
			if (d == 0) q.push({x-1,y,s+B,2});
			if (d == 1) q.push({x+1,y,s+B,3});
			if (d == 2) q.push({x,y-1,s+B,0});
			if (d == 3) q.push({x,y+1,s+B,1});
		}
		if (a[x][y] == '.')
			q.push({x+1,y,s+C,3}),
			q.push({x-1,y,s+C,2}),
			q.push({x,y-1,s+C,0}),
			q.push({x,y+1,s+C,1});
		if (a[x][y] == '<') {
			if (d == 2 || d == 3) q.push({x,y-1,s+D,0});
			if (d == 0) q.push({x,y-2,s,0});
		}
		if (a[x][y] == '>') {
			if (d == 2 || d == 3) q.push({x,y+1,s+D,1});
			if (d == 1) q.push({x,y+2,s,1});
		}
		if (a[x][y] == '^') {
			if (d == 0 || d == 1) q.push({x-1,y,s+D,2});
			if (d == 2) q.push({x-2,y,s,2});
		}
		if (a[x][y] == 'v') {
			if (d == 0 || d == 1) q.push({x+1,y,s+D,3});
			if (d == 3) q.push({x+2,y,s,3});
		}
		if (a[x][y] == 'S')//起点的转移 
			q.push({x+1,y,s,3}),
			q.push({x-1,y,s,2}),
			q.push({x,y-1,s,0}),
			q.push({x,y+1,s,1});
		vis[x][y][d] = 1;
		if (a[x][y] == '.' || a[x][y] == 'S') vis[x][y][2] = vis[x][y][1] = vis[x][y][0] = vis[x][y][3] = 1;
		//优化，如果是这两个四面都标记，不加就T了。。 
		//其实本来是要在转移的时候就判重，只是懒得写 
	}
	return -1;//无解 
}
int main() {
	n = read(), m = read(), A = read(), B = read(), C = read(), D = read();
	for (int i = 1;i <= n;i ++ ) {
		scanf("%s",a[i]+1);
		for (int j = 1;j <= m;j ++ )
			if (a[i][j] == 'S')
				aa[++tot] = make_pair(i,j);
	}
	printf("%d",bfs());
	return 0;
}