刷题记录:牛客NC24605Corn Maze

传送门:牛客

奶牛们去一个 $N\times M$ 玉米迷宫， $\leq N \leq 300,2 \leq M \leq300$ 。
迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。
如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。
玉米迷宫除了唯一的一个出口都被玉米包围。
迷宫中的每个元素都由以下项目中的一项组成：

玉米，# 表示，这些格子是不可以通过的。
草地，. 表示，可以简单的通过。
传送装置，每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
出口，= 表示。
起点， @ 表示
奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。

输入:
5 6
###=##
#.W.##
#.####
#.@W##
######
输出:
3

emmm,一道经典的BFS的题目,加上了一点传送门,虽然不难,但是有一点小坑,需要注意一下

主要思路:

这种跑图的题目,显然我们应该是采用BFS来进行搜索的,并且遇到这种变体的跑图题,一般来说我们可以加上优先队列来代替我们原本的简单队列(反正没有坏处,为了正确性还是直接用吧,虽然可能多次一举)
接下来我们只要不断的进行搜索即可,遇到传送门因为是必须要进行传送的,所以我们直接储存传送们的另一端即可,对于传送门两端点的储存,我们可以在输入时进行一个预处理(先记录上一次出现的字母位置即可,假设不太清楚可以结合最后的代码)
但是在枚举传送门是有一个小坑.当我们经过传送门过去的时候不能将我们的传送门进行一个染色,因为我们有可能需要经过我们的传送过来的传送门回去的,可以结合一下下方的栗子来理解

###=###
#.....#
###A###
#.....#
#@#####
###a..#
#######
(来自洛谷limit的样例),可以看到我们可能只需要借助传送门来进行一个跳板操作

接下来就是我们的代码部分了:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
char mp[400][400];
int n,m;int sx,sy;
int vis[400][400];
struct Node{
	int x,y,flag;
}to[400][400];
Node csm[100];
struct heapnode{
	int x,y,sum;
	bool operator<(const heapnode &rhs) const {
		return sum>rhs.sum;
	}
};
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
void BFS(int x,int y) {
	priority_queue<heapnode>q;//优先队列,保证我们的正确性
	q.push({x,y,0});
	vis[x][y]=1;
	while(!q.empty()) {
		heapnode f=q.top();q.pop();
		if(mp[f.x][f.y]=='=') {
			printf("%d\n",f.sum);
			break;
		}
		for(int i=0;i<=3;i++) {
			int xx=f.x+dx[i],yy=f.y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy]) continue;
			if(to[xx][yy].x!=0) {
				q.push({to[xx][yy].x,to[xx][yy].y,f.sum+1});
			}else {
				q.push({xx,yy,f.sum+1});
				vis[xx][yy]=1;
			}
		}
	}
}
int main() {
	n=read();m=read();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>mp[i][j];
			if(mp[i][j]=='@') {
				sx=i;sy=j;
			}else if(mp[i][j]>='A'&&mp[i][j]<='Z') {//记录传送门
				if(csm[mp[i][j]-'A'].flag!=0) {
					to[csm[mp[i][j]-'A'].x][csm[mp[i][j]-'A'].y].x=i;
					to[csm[mp[i][j]-'A'].x][csm[mp[i][j]-'A'].y].y=j;
					to[i][j].x=csm[mp[i][j]-'A'].x;
					to[i][j].y=csm[mp[i][j]-'A'].y;
					
				}else {
					csm[mp[i][j]-'A'].flag=1;
					csm[mp[i][j]-'A'].x=i;
					csm[mp[i][j]-'A'].y=j;
				}
			}else if(mp[i][j]=='#'){
				vis[i][j]=1;
			}
		}
	}
	BFS(sx,sy);
	return 0;
}