题目

题目描述: 
小明来到一个由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的题目,但是我搞了好久,好久,好久(我不仅憨,还瞎,还傻X)

广度优先遍历:
  1. 关于深度优先遍历并没有很多好说的,就简单讲解一下。
  2. 深度优先遍历就是从一个点开始,将身边一步能抵达的节点进入队列,然后按队列顺序进行操作。
  3. 如果我们的路径权值是一样的,那么队列顺序就是按照权值大小排列的,可以直接使用。
  4. 如果路径权值不同,为了让队列顺序也按照权值大小来,我们当然不能排序,这里就可以用到优先队列(堆结构)了。
  5. 我们上面讲到要按权值大小来排是为什么呢?这当然要看情况,我们的题目一般都要求最小路径,所以我们才会重视顺序。

本题重点讲解
  1. 这道题就是一道简单在平面上面跑地图的bfs,但是有一点不同,就是多了一个传送门
  2. 平面上跑步,咱当然是路径权值一样的,都是1s。但是加了这个传送门以后,传送门是3s的。那么毫无疑问就要用优先队列了。
  3. 所以这道题说复杂其实没有复杂多少,只是相当于在有传送门的位置上,除了上下左右以外,多了一些方向
    (没错!是一些方向!上面说我憨,因为我本来就憨,但是我就是瞎在这里了。我以为一个位置只能有一个传送门,但是题目说了,一个位置可以有多个传送门,传送到多个地方,注意注意!)。
  4. 也就是说我们现在要做的就是,从判断向四个方向上走,变成了向4+n个方向上走罢了。
  5. 最后一个重点:(就是我说我傻X的地方)我们传送过去的点不能做标记!!!
  6. 为啥呢?因为如果我们靠传送过去,并不是最短的方法,那岂不是很亏。
  7. 举个栗子:某一点是传送门,传送到他右边的第一个位置。如果传送,我们要三秒。如果走路,我们只要一秒。484很有道理,标记了我们就走不了了啦。

算法讲解:
  1. 这道题比较重要的就是怎么实现。
  2. 首先,我们和普通bfs一样,需要一个mp数组当地图用,要一个visited数组做路径标记用。
  3. 但是这道题我们要进行传送门传送,所以我们要加一个mark数组用作标记传送门位置(你问我为啥不直接在mp上来?因为这样写代码简单啊,查地图的时候不用分类讨论)。
  4. 标记了传送门位置,我们要知道他传送去哪里了对吧,我们就要一个send数组来保存传送出口
    所以我们这里用了一个三维数组:前二维用来确定地图位置,第三维用来保存终点(终点是二维结构,所以我们用结构体三维数组),为了简单就用vector啦(省的加一个数组保存第三维的长度)。
  5. 为了简单,我们还在外面加了一圈墙,简化越界判断,直接判断是否可以走就行了。为了省空间,几乎都用bool数组,地图只有路和墙,地图和传送门标记就是有或没有。

打代码趴:
  1. 我们输入基础条件,n,m,q。
  2. 然后加一圈墙,并输入墙内的地图。并把传送门位置标记了,记录下出口。
  3. 以上要记得初始化数组
  4. 然后输出bfs的值就好了。
  5. bfs先从起点开始走,然后每个位置进行广度优先遍历。到终点出来,到不了出-1。
  6. 我代码很清晰der!看我代码趴~


AC代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 307;
const int Q = 1e3 + 7;
struct Node {
    int x, y, step;
    bool operator < (const Node b) const {
        return step > b.step;
    }
};
int way[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };//上下左右
bool mp[MAX][MAX], visited[MAX][MAX];//地图,记录,
bool mark[MAX][MAX];//标记传送门
vector<Node> send[MAX][MAX];//传送位置
int sx, sy, ex, ey;
//全局变量区

int bfs();
bool judge(Node x);
//函数预定义区

int main() {
    IOS;
    int n, m, q;//行,列,转送门数量
    while (cin >> n >> m >> q) {
        for (int i = 1; i <= m; i++)
            mp[0][i] = mp[n + 1][i] = false;
        for (int i = 1; i <= n; i++)
            mp[i][0] = mp[i][m + 1] = false;
        //我们用true表示空地,false表示墙,上面在外面加一圈墙
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                char ch; cin >> ch;
                if ('S' == ch) sx = i, sy = j;
                else if ('T' == ch) ex = i, ey = j;
                //判断起点和终点
                if ('#' == ch) mp[i][j] = false;
                else mp[i][j] = true;
                //判断墙和空地
            }
        memset(mark, 0, sizeof mark);
        memset(send, 0, sizeof send);
        for (int i = 1; i <= q; i++) {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            x1++; y1++; x2++; y2++;
            mark[x1][y1] = true;
            send[x1][y1].push_back(Node{ x2, y2 });
        }
        cout << bfs() << endl;
    }
    return 0;
}
int bfs() {
    priority_queue<Node> que;
    que.push(Node{ sx, sy, 0 });
    memset(visited, 0, sizeof visited);
    visited[sx][sy] = true;
    //我们用true表示走过,false表示没走过
    while (!que.empty()) {
        Node top = que.top(); que.pop();
        //拿出队首元素
        if (ex == top.x && ey == top.y) return top.step;
        //判断是否为终点
        if (mark[top.x][top.y])
            for (int i = send[top.x][top.y].size() - 1; i >= 0; i--) {
                Node nxt = send[top.x][top.y][i];
                if (judge(nxt)) {
                    nxt.step = top.step + 3;
                    que.push(nxt);
                    //visited[nxt.x][nxt.y] = true;(不能加)
                }
            }
        //这个点是传送门
        for (int i = 0; i < 4; i++) {
            Node nxt{ top.x + way[i][0], top.y + way[i][1], top.step + 1 };
            if (judge(nxt)) {
                que.push(nxt);
                visited[nxt.x][nxt.y] = true;
            }
        }
        //加入周围四个点
    }
    return -1;
}
bool judge(Node x) {
    if (!mp[x.x][x.y]) return false;
    if (visited[x.x][x.y]) return false;
    return true;
}
//函数区