nc15665 maze 题解（传送门）广搜bfs+优先队列

妖狐艹你老母 2023-03-02 10:57 23阅读 0赞

maze:[原题链接][Link 1]

##### 题目描述： #####

> 小明来到一个由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;
    }

[Link 1]: https://ac.nowcoder.com/acm/problem/15665