题目
题目描述: 小明来到一个由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; } //函数区