最短路径C++

问题描述

小蓝有一天误入了一个混境之地。
好消息是: 他误打误撞拿到了一张地图,并从中获取到以下信息:

• 混境之地是一个 n·m巨细的矩阵，此中#表现墙，无法通行，.表现普通的道路，k表现散落在地图中的钥匙。
  
• 他如今所在位置的坐标为(A,B)，而这个混境之地出口的坐标为(C,D),当站在出口时且携带最少一把钥匙即表现可以逃离混境之地。
  
• 地图中大概存在不止一把钥匙。
  

坏消息是:

• 地图中大概没有钥匙。
  

小蓝可以往上下左右四个方向行走，每走一步耗时一分钟。
小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，输出最少需要消耗多少时间，反之输出-1。
输入格式

第一行输入两个正整数 n, m, 表现矩阵的巨细。
第二行输入四个正整数 A, B, C, D, 表现小蓝当前所在位置的坐标，以及混境之地出口的坐标。
接下来输入 n行, 每行 m个字符, 表现混境之地的地图, 此中#表现墙, 无法通行, .表现普通的道路, k表现散落在地图中的钥匙。
输特别式

输出数据共一行一个字符串:

• 若小蓝可以逃离混境之地, 则输出最少需要消耗多少时间。
  
• 若小蓝无法逃离混境之地, 则输出 -1。
  

样例输入1

1. 5 5
2. 1 1 5 5
3. ....#
4. #..#..
5. k.#..
6. .#...
7. ...#.

复制代码

样例输出1

1. 12

复制代码

样例表明1

从(1,1)到(5,5)的最短道路为:

• (1,1) → (1,2) → (2,2) → (3,2) → (3,1) 拿到钥匙。
  
• (3,1) → (4,1) → (5,1) → (5,2) → (5,3) → (4,3) → (4,4) → (4,5) → (5,5) 到达尽头。
  

问题思绪

本质上这是一个考 最短路径 的问题，用 BFS 办理
有两种情况
1. 图上只有一个钥匙
由于图上只有一个钥匙，且出去的条件中需要一把钥匙。即我们必须颠末钥匙的位置。
假设我到钥匙的路径间隔为w，钥匙到出口路径的间隔为d。
由于走一步算一分钟，则总时长=w+d
关键：
计算 我到钥匙的最短路径 + 钥匙到出口的最短路径
有两个方案：
（1）把钥匙作为出发点，求钥匙-》我的最短路径 + 钥匙-》出口的最短路径。相加得到总体的最短路径
（2）把钥匙作为尽头，求 我-》钥匙的最短路径 + 尽头-》钥匙的最短路径相加得到总体的最短路径
2. 图上有多个钥匙
由于图上有多个钥匙，为了求最短路径，我们需要找出哪个钥匙到起点和尽头的最短路径更短。

• 如果按照方案一去求，钥匙大概在的点数为（n×m），点的数量为（n×m）那么时间复杂度最坏的情况下为 O(n2⋅m2)，时间复杂度较高。
  
• 如果按照方案二区求，则对起点和尽头进行 BFS，由于点的数量为 n·m ，故时间复杂度为 O(n·m)，在罗列所有的钥匙的情况下，钥匙的数量最多为 n·m罗列的复杂度为 O(n·m)，计算的时间复杂度为O(1)，故总体复杂度为O(n·m+n·m)，即O(n·m)，时间复杂度较低，选择方案二
  

思绪

代码

1. #include <iostream>
2. #include <cstring>
3. #include <algorithm>
4. #include <queue>
6. #define x first
7. #define y second
9. using namespace std;
11. typedef pair<int, int> PII;
13. const int N = 1e3 + 10;
15. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
17. int n, m;
18. int A, B, C, D;
19. char g[N][N];
20. vector<vector<int>> dist1, dist2;
22. void bfs(int x, int y, vector<vector<int>> &dist)
23. {
24.     dist[x][y] = 0;
25.     queue<PII> q;
26.     q.push({x, y});
27.    
28.     while (q.size())
29.     {
30.         auto t = q.front();
31.         q.pop();
32.         
33.         for (int i = 0; i < 4; ++ i )
34.         {
35.             int tx = t.x + dx[i], ty = t.y + dy[i];
36.             if (tx < 0 || ty < 0 || tx >= n || ty >= m || g[tx][ty] == '#')
37.                 continue;
38.             if (dist[tx][ty] <= dist[t.x][t.y] + 1)
39.                 continue;
40.             dist[tx][ty] = dist[t.x][t.y] + 1;
41.             q.push({tx, ty});
42.         }
43.     }
44. }
46. int main()
47. {
48.     cin >> n >> m;
49.     cin >> A >> B >> C >> D;
50.     A --, B --, C --, D --;
51.    
52.     for (int i = 0; i < n; ++ i )
53.         cin >> g[i];
54.    
55.     dist1 = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f));
56.     dist2 = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f));
57.    
58.     bfs(A, B, dist1);
59.     bfs(C, D, dist2);
60.    
61.     int res = 0x3f3f3f3f;
62.     for (int i = 0; i < n; ++ i )
63.         for (int j = 0; j < m; ++ j )
64.             if (g[i][j] == 'k')
65.                 res = min(res, dist1[i][j] + dist2[i][j]);
66.    
67.     if (res == 0x3f3f3f3f)
68.         puts("-1");
69.     else
70.         cout << res << endl;
71.    
72.     return 0;
73. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。