maze【BFS】

链接：https://ac.nowcoder.com/acm/problem/15665?&headNav=acm
来源：牛客网

题目描述
小明来到一个由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的裸题了，当然由于多了个传送阵，所以要考虑每个点能传送到的后续结点的个数，由于可能不止一个，所以用vector来存。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define eps 1e-8
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(x, y) make_pair(x, y)
#define Min_3(a, b, c) min(a, min(b, c))
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int dir[4][2] =
{
    -1, 0,
    0, -1,
    0, 1,
    1, 0
};
const int maxN = 305;
int N, M, Q, dis[maxN][maxN];
inline bool In_Map(int x, int y) { return x >= 0 && y >= 0 && x < N && y < M; }
char mp[maxN][maxN];
vector<pair<int, int>> vt[maxN][maxN];
struct node
{
    int x, y, dis;
    node(int a=0, int b=0, int c=0):x(a), y(b), dis(c) {}
    friend bool operator < (node e1, node e2) { return e1.dis > e2.dis; }
} now;
priority_queue<node> que;
inline int bfs(int x, int y)
{
    for(int i=0; i<N; i++) for(int j=0; j<M; j++) dis[i][j] = INF;
    dis[x][y] = 0;
    while(!que.empty()) que.pop();
    que.push(node(x, y, 0));
    while(!que.empty())
    {
        now = que.top(); que.pop();
        if(mp[now.x][now.y] == 'T') return now.dis;
        x = now.x; y = now.y;
        if(dis[x][y] < now.dis) continue;
        for(int i=0, xx, yy; i<4; i++)
        {
            xx = x + dir[i][0]; yy = y + dir[i][1];
            if(!In_Map(xx, yy) || mp[xx][yy] == '#' || dis[xx][yy] <= dis[x][y] + 1) continue;
            dis[xx][yy] = dis[x][y] + 1;
            que.push(node(xx, yy, dis[xx][yy]));
        }
        int len = (int)vt[x][y].size();
        for(int i=0, xx, yy; i<len; i++)
        {
            xx = vt[x][y][i].first; yy = vt[x][y][i].second;
            if(!In_Map(xx, yy) || mp[xx][yy] == '#' || dis[xx][yy] <= dis[x][y] + 3) continue;
            dis[xx][yy] = dis[x][y] + 3;
            que.push(node(xx, yy, dis[xx][yy]));
        }
    }
    return -1;
}
int main()
{
    int sx, sy;
    while(scanf("%d%d%d", &N, &M, &Q) != EOF)
    {
        for(int i=0; i<N; i++) scanf("%s", mp[i]);
        for(int i=0; i<N; i++) for(int j=0; j<M; j++) vt[i][j].clear();
        for(int i=1, u1, u2, v1, v2; i<=Q; i++)
        {
            scanf("%d%d%d%d", &u1, &u2, &v1, &v2);
            vt[u1][u2].push_back(MP(v1, v2));
        }
        for(int i=0; i<N; i++) for(int j=0; j<M; j++) if(mp[i][j] == 'S') { sx = i; sy = j; }
        printf("%d\n", bfs(sx, sy));
    }
    return 0;
}