【每日一题】maze
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。
解析
这是一道非常简单的bfs的题目，但是我搞了好久，好久，好久（我不仅憨，还瞎，还傻X）。
广度优先遍历：
- 关于深度优先遍历并没有很多好说的，就简单讲解一下。
- 深度优先遍历就是从一个点开始，将身边一步能抵达的节点进入队列，然后按队列顺序进行操作。
- 如果我们的路径权值是一样的，那么队列顺序就是按照权值大小排列的，可以直接使用。
- 如果路径权值不同，为了让队列顺序也按照权值大小来，我们当然不能排序，这里就可以用到优先队列（堆结构）了。
- 我们上面讲到要按权值大小来排是为什么呢？这当然要看情况，我们的题目一般都要求最小路径，所以我们才会重视顺序。
本题重点讲解：
- 这道题就是一道简单在平面上面跑地图的bfs，但是有一点不同，就是多了一个传送门。
- 平面上跑步，咱当然是路径权值一样的，都是1s。但是加了这个传送门以后，传送门是3s的。那么毫无疑问就要用优先队列了。
- 所以这道题说复杂其实没有复杂多少，只是相当于在有传送门的位置上，除了上下左右以外，多了一些方向
（没错！是一些方向！上面说我憨，因为我本来就憨，但是我就是瞎在这里了。我以为一个位置只能有一个传送门，但是题目说了，一个位置可以有多个传送门，传送到多个地方，注意注意！）。 - 也就是说我们现在要做的就是，从判断向四个方向上走，变成了向4+n个方向上走罢了。
- 最后一个重点：（就是我说我傻X的地方）我们传送过去的点不能做标记！！！
- 为啥呢？因为如果我们靠传送过去，并不是最短的方法，那岂不是很亏。
- 举个栗子：某一点是传送门，传送到他右边的第一个位置。如果传送，我们要三秒。如果走路，我们只要一秒。484很有道理，标记了我们就走不了了啦。
算法讲解：
- 这道题比较重要的就是怎么实现。
- 首先，我们和普通bfs一样，需要一个mp数组当地图用，要一个visited数组做路径标记用。
- 但是这道题我们要进行传送门传送，所以我们要加一个mark数组用作标记传送门位置（你问我为啥不直接在mp上来？因为这样写代码简单啊，查地图的时候不用分类讨论）。
- 标记了传送门位置，我们要知道他传送去哪里了对吧，我们就要一个send数组来保存传送出口。
所以我们这里用了一个三维数组：前二维用来确定地图位置，第三维用来保存终点（终点是二维结构，所以我们用结构体三维数组），为了简单就用vector啦（省的加一个数组保存第三维的长度）。 - 为了简单，我们还在外面加了一圈墙，简化越界判断，直接判断是否可以走就行了。为了省空间，几乎都用bool数组，地图只有路和墙，地图和传送门标记就是有或没有。
打代码趴：
- 我们输入基础条件，n，m，q。
- 然后加一圈墙，并输入墙内的地图。并把传送门位置标记了，记录下出口。
- 以上要记得初始化数组。
- 然后输出bfs的值就好了。
- bfs先从起点开始走，然后每个位置进行广度优先遍历。到终点出来，到不了出-1。
- 我代码很清晰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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
投递中国南方电网等公司10个岗位 >
