maze

题目链接：https://ac.nowcoder.com/acm/problem/15665

题目描述

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

示例

输入

5 5 1
..S..
…..
.###.
…..
..T..
1 2 3 3
5 5 1
..S..
…..
.###.
…..
..T..
3 3 1 2
5 5 1
S.#..
..#..
###..
…..
….T
0 1 0 2
4 4 2
S#.T
.#.#
.#.#
.#.#
0 0 0 3
2 0 2 2

输出

6
8
-1
3

分析

本题是普通迷宫问题的变种，但仍是在求迷宫中某点是否可达，以及其路径长度(本题为耗费时间)，因此我们的主要思路依然为广搜。
回忆一下，通常我们广搜就是按照远近，从近到远挨着搜，本题中传送阵的出现虽然有所变化，但仅仅是扩充了试探的原则，不仅仅是”挨着搜”，增加了传送阵搜，其余不变，因此为了保持由近及远的原则，我们可以使用优先队列，出队顺序由耗时决定。
以上即为本题主要思路，还有一些细节均在代码注释中不再赘述。

AC代码

---

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
 
struct pos
{
    int x,y;
    int time;
    pos (int X=0,int Y=0,int Time=0)
    {
        x=X;
        y=Y;
        time=Time;
    }
    bool operator < (const pos &a) const
    {
        return this->time >= a.time;   //重载要注意
    }
};  //注意，优先队列内部排序时虽然利用小于号，但却是大的在前，我们这要求小的在前
 
 
int n,m,q;
int t,s;
bool visited[300][300];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool mp[300][300];          //记录地图
int dis[300][300];          //记录从起点到各点所需时间
priority_queue<pos> Q;      //优先队列 排序标准为到达该点的时间
map<int,vector<int>> z;     //存储传送阵的数据 每一个int数表示坐标(行编号*列数+列编号)
                            //因为某个点可能是多个传送阵的起点，故此处使用vector
int bfs()
{
    while(!Q.empty())
    {
        int x=Q.top().x;
        int y=Q.top().y;
        int time=Q.top().time;
        if(x*m+y==t) return time;   //注意出队时一个点的最短时间才被确定 因此终点判断放在这
        Q.pop();
        if(visited[x][y]) continue; //由于传送阵的存在某个点可能在队列中不止一个 先出来的时间最短
        dis[x][y]=time;             //并将之记录
        visited[x][y]=true;         //出队后才标记该点数据已定
        //首先试探邻近点
        for(int i=0;i<4;i++)
        {
            int newx=x+dir[i][0];
            int newy=y+dir[i][1];
            if(newx<0||newy<0||newx>=n||newy>=m)
                continue;
            if(visited[newx][newy])
                continue;
            if(!mp[newx][newy])
                continue;
            Q.push(pos(newx,newy,dis[x][y]+1));
        }
        //再试探传送
        for(int i=0;i<z[x*m+y].size();i++)
        {
            int newx=z[x*m+y][i]/m;
            int newy=z[x*m+y][i]%m;
            if(!mp[newx][newy])
                continue;
            if(visited[newx][newy])
                continue;
            Q.push(pos(newx,newy,dis[x][y]+3));
        }
    }
    return -1;
}
int main()
{
    while(cin >> n >> m >> q)
    {
        cin.get();
        memset(visited,0,sizeof(visited));
        z.clear();
        while(!Q.empty()) Q.pop();
        for(int i=0;i<n;i++)
        {
            string temp;
            getline(cin,temp);
            for(int j=0;j<m;j++)
            {
                if(temp[j]=='#')
                {
                    mp[i][j]=false;
                    continue;
                }
                mp[i][j]=true;
                if(temp[j]=='S')
                {
                    Q.push(pos(i,j,0)); //起点入队
                    s=i*m+j;
                }
                else if(temp[j]=='T')   t=i*m+j;
            }
        }
        for(int i=0;i<q;i++)    //存储传送阵的数据
        {
            int x1,y1,x2,y2;
            cin >>x1>>y1>>x2>>y2;
            z[x1*m+y1].push_back(x2*m+y2);
        }
        cout << bfs() << endl;
    }
    return 0;
}