洛谷 P4872 OIer们的东方梦 题解

前言

一个下午，一个晚上，一个早上，可以算是一天了吧，终于调出了这道题，纪念一下吧！！！

食用更佳。

这道题其实就是一道简简单单的 BFS 模（du）板（liu）题。

说难不难，简单不简单，虽然没有难的算法，但是就是码量一百多行，比较难调。

题目难度绿，思维难度橙，代码难度蓝。真是个绝世好题。

题目意思

就是一个最短路问题，开个优先队列跑 BFS。有很多种路，需要逐个 if 判断过去。

为了后面讲解，我们设置一个 id 代表拿的太阳花或者剑的状态（具体见代码）。

如果你逐个查找每个传送门会卡成 \(O(N^4)\)。如果我们要去间隙传送门，那么必然是为了一次性传送，或者传去其他地方拿个太阳花或者剑之类的。所以这样暴力的算法就会使其有可能会从这个传送门跳到另一个传送门，然后什么东西也没拿就跳回又另一个传送门。然后我们会发现因为你每次到的都是 step 最小的点，所以只要你有一次跳到了这个点传送门，那么在当前的 id 下乱跳间隙的 step 是最优的，所以代码中再开一个 vis2 数组来表示 id 下是否记录了这些传送门的点。因为 id 最多是 \(3\)，是个小常数，可以忽略，因此复杂度降到 \(O(N^2)\)。

注意事项

本题有很多细节需要注意。

• BFS 开始 vis 数组没有初始化起点（一般人应该也不会有这个问题）但我经常这样。
• X、S、E在判断的时候是相当于空地的，是可以直接走过的，不要忽略。
• 重载函数别写错了。

本人犯的最大错误

因为整个程序都是依靠着优先队列实现最优解的保持，但是由于本人结构体重载函数学的不好，所以把符号写反了 （尽管嘲讽。

接下来讲一下结构体重载函数的写法。

struct data{
	int x,y;
}a[N];

以上是一个结构体标准写法。如果我们想对 a 排序，按照 x 从小到大排序，那么我们可以写一个 cmp 函数。

bool cmp(data a,data b) {
	return a.x<b.x;
}

但是优先队列等无法写自定义函数的时候，就得用到结构体重载函数，就是在结构体内部定义函数。下面介绍其中一种写法。

struct data{
	int x,y;
   friend bool operator<(const struct data &a,const struct data &b){
		return a.step > b.step;
	}
}a[N];

反正 friend 开头那一行就背下来就好了，虽然我不知道为什么。就是觉 C++ 创始人很奇怪，这还要加 const，struct…… 注意了，还要加取地址符。

感觉很奇怪！

然后函数里的内容就要跟 cmp 写法基本一样了，但是重点是：他的符号跟 cmp 是反的！，所以从小到大排序要用大于符号！（我就挂在这了）。

最后，附上 AC code：（注释齐全，自认马蜂良好，容易理解）。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl "\n"
using namespace std;
const int N = 1005;
int n,m;
string c[N];
int vis[N][N][3],vis2[3];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node{
	int x,y,step;
	bool sun;//是否遇到过太阳花
	bool jian;//是否有楼观剑
	friend bool operator<(const struct node &a,const struct node &b){
		return a.step > b.step;
	}
};
struct data{
	int x,y;
}s[N*N];int si;
int bx,by,ex,ey;//设置起点和终点
bool check(int x,int y){//判断边界情况
	if(x<1||x>n||y<1||y>m)return true;
	return false;
}
int getid(node x){
	if(x.jian) return 2;
	if(x.sun) return 1;
	return 0;
}
int main(){
	memset(vis,0x3f,sizeof vis);
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> c[i];
		c[i]=' '+c[i];
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(c[i][j]=='M')c[i][j]='0';//麻薯都说吃了没用，还不如不吃！
			else if(c[i][j]=='S')bx=i,by=j,c[i][j]='0';
			else if(c[i][j]=='E')ex=i,ey=j,c[i][j]='0';
			else if(c[i][j]=='X')s[++si].x=i,s[si].y=j;
		}
	}
	priority_queue<node> q;
	vis[bx][by][0]=0;
	q.push({bx,by,0,0,0});
//	cout<<bx<<" "<<by<<endl;
	while(!q.empty()){
		node f=q.top();
		q.pop();
//		cout<<f.x << " "<< f.y<<endl;
		if(f.x==ex && f.y==ey) {
			cout<<f.step;
			return 0;
		}
		int nowid = getid(f);
		for(int i = 0 ;i < 4;i++){
			int xx=f.x + dx[i];
			int yy=f.y + dy[i];
			if(check(xx,yy)) continue;
			if(c[xx][yy] == '0' || c[xx][yy]=='X'){//是空地
				if(vis[xx][yy][nowid] > f.step+1){//如果比最短路径短，那么就走
					vis[xx][yy][nowid] = f.step+1;
					q.push({xx,yy,f.step+1,f.sun,f.jian});
				}
			}else if(c[xx][yy]=='1'){//是墙
				if(f.jian){//有jian才能走
					if(vis[xx][yy][nowid] > f.step+1){
						vis[xx][yy][nowid] = f.step+1;
						q.push({xx,yy,f.step+1,f.sun,f.jian});
					}	
				}
			}else if(c[xx][yy]=='2'){//是little 妖怪
				if(f.jian||f.sun){//有剑或太阳花，把你斩了
					if(vis[xx][yy][nowid] > f.step+1){
						vis[xx][yy][nowid] = f.step+1;
						q.push({xx,yy,f.step+1,f.sun,f.jian});
					}	
				}else{//没剑，花3s把你干了，再加上1s移动时间
					if(vis[xx][yy][nowid] > f.step+4){
						vis[xx][yy][nowid] = f.step+4;
						q.push({xx,yy,f.step+4,f.sun,f.jian});
					}						
				}		
			}else if(c[xx][yy]=='3'){//big 妖怪
				if(f.jian||f.sun){//有剑或太阳花，把你斩了
					if(vis[xx][yy][nowid] > f.step+1){
						vis[xx][yy][nowid] = f.step+1;
						q.push({xx,yy,f.step+1,f.sun,f.jian});
					}	
				}else{//没剑，花8s把你干了，再加上1s移动时间
					if(vis[xx][yy][nowid] > f.step+9){
						vis[xx][yy][nowid] = f.step+9;
						q.push({xx,yy,f.step+9,f.sun,f.jian});
					}						
				}		
			}else if(c[xx][yy]=='4'){//太阳花
				if(vis[xx][yy][max(1,nowid)] > f.step+1){
					vis[xx][yy][max(1,nowid)] = f.step+1;
					q.push({xx,yy,f.step+1,1,f.jian});
				}
			}else if(c[xx][yy]=='5'){//是jian
				if(vis[xx][yy][2] > f.step+1){
					vis[xx][yy][2] = f.step+1;
					q.push({xx,yy,f.step+1,f.sun,f.jian});
				}
				if(vis[xx][yy][nowid] > f.step+6){
					vis[xx][yy][nowid] = f.step+6;
					q.push({xx,yy,f.step+6,f.sun,1});
				}								
			}
		}
		int xx=f.x,yy=f.y;
		if(c[xx][yy]=='X'){
			if(vis2[getid(f)])continue;vis2[getid(f)]=1;
			for(int i = 1;i <= si;i++){
				if(s[i].x==xx&&s[i].y==yy) continue;
				if(vis[s[i].x][s[i].y][nowid] > f.step+1){
					vis[s[i].x][s[i].y][nowid] = f.step+1;
					q.push({s[i].x,s[i].y,f.step+1,f.sun,f.jian});
				}					
			}
		}
	}
	cout<<"We want to live in the TouHou World forever";
	return 0;
}

广告。