自动搬运

查看原文

来自洛谷，原作者为

	Flandre_495 天魔山巅雪驹草，三途河畔彼岸花

搬运于2025-08-24 22:04:47，当前版本为作者最后更新于2019-09-06 19:10:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

调了一天，终于过了~写篇题解纪念一下~

感觉我的代码比起其他人的可读性要高许多。。。

感谢disangan233提供神仙题面，感谢上海爱丽丝幻乐团提供信仰，能有信心磕这道题的估计大部分是車万党吧。。。

废话不多说：我们先来分析一下题：

这题细节很多，过样例却WA掉的可以看看代码中的具体注释。

我采用了优先队列BFS的方法，于是每个点有几个属性：坐标，dis值，是否抢剑，是否偷花。

我们再定义一个NB值，什么都没有时NB=0，有花时NB=1，有剑时NB=2.

分析每个字符：

0,1,2,3都好说，就是NB值不一样时距离不同。

4:偷花不需要时间，可以直接修改属性。

5:注意可以不要剑，所以要考虑要和不要两种情况。

M:关于麻薯。。。藏起来就好，别让幽幽子看到。

X:最麻烦的一个，可以满地图乱窜，每次都枚举复杂度是不行的，但是你发现每个NB值状态下最多只用传送一次就行，没必要传来传去，直接传到最后一次的位置不就行了。除非你专程去偷花或抢剑，那样会使你的NB值增加，所以每个NB值下都可以考虑传送，传送过就可以忽略X了。

那就看代码吧：具体操作都在代码里了~

自我感觉可读性良好。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define QWQ cout<<"QwQ"<<endl;
#define ll long long 
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const int N=101010;
const int qwq=303030;
const int inf=0x3f3f3f3f;
int n,m;
int g,h,s,t;                         //起点和终点的坐标 
char z[1234][1234];
int dis[1234][1234][3];              //每个NB值状态下的dis值 
bool bayunzi[4];                     //在这个NB值状态下是否用过间隙 
int ff[] = {1,0,0,-1};
int gg[] = {0,1,-1,0};               //4个方向 
struct E{
	int d;
	int i,j; 
	bool lou,hua;                    //lou：是否有楼观剑，hua：是否抢过花 
};
priority_queue <E> q;                //优先队列，对d优先 
inline bool operator < (E aa,E bb) { return aa.d > bb.d; }

inline int getNB(E v) {             //获得NB值 
	if(v.lou) return 2;
	if(v.hua) return 1;
	return 0;
}

inline void check(E v) {            //更新dis值，并压入队列 
	int NB = getNB(v);
	if(v.d >= dis[v.i][v.j][NB]) return ;
	dis[v.i][v.j][NB] = v.d;     q.push(v);
}

void jian_xi(E u) {                     //从间隙往别的间隙走 
	int NB = getNB(u);
	if(bayunzi[NB]) return ; bayunzi[NB] = 1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) {
		if(z[i][j]!='X') continue;
		E v = (E){u.d+1, i, j, u.lou, u.hua};
		check(v);
	}
}

int BFS() {
	memset(dis,0x3f,sizeof(dis));
	q.push( (E){0,g,h,0,0} );
	while(!q.empty()) {
		E u = q.top(); q.pop();
		if(u.i==s && u.j==t) return u.d;    //终于到终点了！
		for(int k=0;k<4;k++) {              //4个方向 
			E v; 
			v.lou = u.lou; 
			v.hua = u.hua;
			v.i = u.i + ff[k];
			v.j = u.j + gg[k];             //下一个点的信息 
			int NB = getNB(v);
			if(v.i<0 || v.j<0 || v.i>n || v.j>m) continue;  //边界 
			int cl = z[v.i][v.j];           
			if(cl=='1') {
				v.d = u.d + 1;
				if(NB==2) check(v);         //楼观剑砍墙 
			}
			if(cl=='0' || cl=='X') {        //注意：‘X’是可以穿的！
				v.d = u.d + 1;
				check(v);
			}
			if(cl=='2') {
				if(NB!=0) v.d = u.d + 1;
				else      v.d = u.d + 4;    //不同NB值状态下距离不同。 
				check(v);
			}
			if(cl=='3') {
				if(NB!=0) v.d = u.d + 1;
				else      v.d = u.d + 9; 
				check(v);
			}
			if(cl=='4') {
				v.d = u.d + 1; v.hua = 1;   //偷花。
				check(v);
			}
			if(cl=='5') {                   //注意楼观剑要check两次，因为可以不选。 
				v.d = u.d + 1; 
				check(v); 
				if(!v.lou) v.lou = 1, v.d += 5;           //获得需5秒 
				check(v);
			}
		}
		if(z[u.i][u.j]=='X') jian_xi(u);                  //从间隙飞 
	}
	return -1;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",z[i]+1);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) {
		if(z[i][j]=='M') z[i][j] = '0';                  //把麻薯变成0藏起来，别让幽幽子吃了。 
		if(z[i][j]=='S') g = i, h = j, z[i][j] = '0';    //注意起点是可以走好几次的，它的属性改成0。
		if(z[i][j]=='E') s = i, t = j, z[i][j] = '0';    
	}
	int ans = BFS();
	if(ans!=-1) printf("%d",ans);
	else printf("We want to live in the TouHou World forever");    //此生无悔入东方，来世炸了幻想乡。 
	return 0;
}

看起来长，其实很瘦的，压下行就短了:)