bfs

题意

小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。

小明只能向上下左右相邻的格子移动，每移动一次花费1秒。

有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

分析

如果没上雨神的课，这道题我会做的够呛。关键是对bfs的理解。
如课上所说的，我们使用bfs标记每一个到达每一个方块的最短时间。如果，我们遍历到这个方块，而我们现在到这个方块的时间大于等于这个方块上所标记的时间，那我们便应该忽视该方块！不放在队列中，也不进行改动。
这样bfs一下来，每一个方块上都标记了，我们到他的最短时间。不能到达的为初始的INF。

代码如下、注意细节

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int max_n = 350;
const int max_q = 1500;
const int INF = 1e9;
int vis[max_n * max_n];
int ans[max_n * max_n];
int n, m, q;
int start, End;

int bfs() {
    int p1, p2, p3, p4;
    deque<int> que;ans[start] = 0;
    que.push_back(start);
    while (!que.empty()) {
        int cur = que.front();que.pop_front();
        p1 = cur - 1;p2 = cur + 1;
        p3 = cur - m;p4 = cur + m;
        if (cur % m != 0 && vis[p1]) {
            if (ans[p1] > ans[cur] + 1) {
                ans[p1] = ans[cur] + 1;
                que.push_back(p1);
            }
        }
        if (p2 % m != 0 && vis[p2]) {
            if (ans[p2] > ans[cur] + 1) {
                ans[p2] = ans[cur] + 1;
                que.push_back(p2);
            }
        }
        if (p3 >= 0 && vis[p3]) {
            if (ans[p3]> ans[cur] + 1) {
                ans[p3] = ans[cur] + 1;
                que.push_back(p3);
            }
        }
        if (p4 < m*n && vis[p4]) {
            if (ans[p4] > ans[cur] + 1) {
                ans[p4] = ans[cur] + 1;
                que.push_back(p4);
            }
        }
        if (vis[cur] > INF) {
            int p5 = vis[cur] - INF;
            if (ans[p5] > ans[cur] + 3) {
                ans[p5] = ans[cur] + 3;
                que.push_back(p5);
            }
        }
    }
    if (ans[End] == INF)return -1;
    return ans[End];
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> n >> m >> q) {
        char ch;fill(vis, vis + max_n * max_n, 2);
        fill(ans, ans + max_n * max_n, INF);
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                cin >> ch;
                if (ch == 'S')start = i * m + j;
                else if (ch == '#')vis[i * m + j] = 0;
                else if (ch == 'T')End = i * m + j;
            }
        }int x1, y1, x2, y2;
        for (int i = 0;i < q;i++) {
            cin >> x1 >> y1 >> x2 >> y2;
            if (!vis[x1 * m + y1] || !vis[x2 * m + y2])continue;
            vis[x1 * m + y1] = INF + x2 * m + y2;
        }
        cout << bfs() << endl;
    }
}