nc15665 maze 题解 （传送门） 广搜bfs+优先队列_小明来到一个由n x m个格子组成的迷宫,有些格子是陷阱,用

maze:原题链接

题目描述：

小明来到一个由n x m个格子组成的迷宫 ，有些格子是陷阱，用’#‘表示，小明进入陷阱就会死亡，’.'表示没有陷阱。小明所在的位置用’S’表示，目的地用’T’表示。
小明只能向上下左右相邻的格子移动，每移动一次花费1秒。
有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。
一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

输入描述：

有多组数据。对于每组数据： 第一行有三个整数n,m,q
(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。 最后q行，每行四个整数x1,y1,x2,y2 (0≤ x1,x2< n,0≤ y1,y2< m)，表示一个传送阵的入口在x1行y1列，出口在x2行y2列。

输出描述：

如果小明能够活着到达目的地，则输出最短时间，否则输出-1。

---

思路：

这是一道经典的bfs+优先队列问题。

求最短路径，首先考虑使用bfs，但此处的bfs和平时有些不同，题目中加了传送门，传送门能传送到出口，但耗时3秒，我们还要考虑用不用传送门，如果直接从入口走到出口的时间都没有3秒，那么就不需要开启传送门。

所以这道题bfs的费用就不是步数了，而是时间，因为有可能步数长但时间少，所以我们可以使用一个优先队列，重载其判断标准，让距离起点时间最短的点放在队首（普通bfs是让距离起点步数最少的点放在队首）。

而对于传送门的处理可以看作对入口能到的下一个点增多了，不止能到上下左右四个点，还能到其传送门的出口点。
若走传送门，到达终点我们不标记（不改变vis的值），因为我们不确定走传送门近还是不走近，但正常走一定是最近的，所以只标记正常扩展的点。

此处对于传送门的存储也是一个问题，在代码中有解释

代码解析：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 310;
struct node
{
	int x,y,s;
	bool operator < (const node & t)const{	//重载运算符，按照s的升序排列，队首的费用s最小
		return s > t.s;
	}
};

int n,m,p,sx,sy,ex,ey;	//（sx，sy）起点坐标，（ex，ey）终点坐标
char e[N][N];	//地图
bool vis[N][N];	//标记数组，走过的点记为1
node cv[N][N];	//传送门记录数组，cv[a][b].x（或.y），说明（a，b）处有传送门终点是（x，y），cv[a][b].s = 1说明（a，b）处有传送门
priority_queue<node> q;	//优先队列
int ne[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};	//方向数组

int bfs()
{
	while(!q.empty())	//清空队列
		q.pop();
	vis[sx][sy] = 1;	//标记起点
	q.push({sx,sy,0});	//起点入队
	while(!q.empty())
	{
		int nx = q.top().x;	//记录队首的x，y，s
		int ny = q.top().y;
		int ns = q.top().s;
		if(nx == ex && ny == ey)	//如果是终点返回其时间
			return ns;
		q.pop();	//队首出队
		if(cv[nx][ny].s == 1 && vis[cv[nx][ny].x][cv[nx][ny].y] == 0)	//若（nx，ny）此处有传送门并且终点未走到过，我们考虑开启传送门
			q.push({cv[nx][ny].x,cv[nx][ny].y,ns+3});	//传送门的终点入队，但此处我们不标记
		for(int i = 0;i < 4;i++)	//向四个方向正常扩展
		{
			int tx = nx + ne[i][0];
			int ty = ny + ne[i][1];
			if(tx < 0 || ty < 0 || tx >= n || ty >= m)	//判断是否出界
				continue;
			if((e[tx][ty] == '.' || e[tx][ty] == 'T') && vis[tx][ty] == 0)	//判断是否可走
			{
				vis[tx][ty] = 1;
				q.push({tx,ty,ns+1});
			}
		}
	}
	return -1;	//若未找到出口，返回-1
}

int main()
{
	while(cin >> n >> m >> p)
	{
		memset(vis,0,sizeof vis);	
		memset(cv,0,sizeof cv);	//重置标记数组和传送门数组
		for(int i = 0;i < n;i++)
		{
			for(int j = 0;j < m;j++)
			{
				cin >> e[i][j];
				if(e[i][j] == 'S')	//记录起点和终点
					sx = i,sy = j;
				if(e[i][j] == 'T')
					ex = i,ey = j;
			}
		}
		while(p--)
		{
			int a,b,c,d;
			cin >> a >> b >> c >> d;
			if(e[a][b] == '#' || e[c][d] == '#')	//若传送门的起点或终点是陷阱，此传送门必不可用，我们直接不存，减小时间空间
				continue;
			cv[a][b].x = c;
			cv[a][b].y = d;	//存储终点坐标
			cv[a][b].s = 1;	//此处的s记为1，说明有传送门
		}
		cout << bfs() << endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83