数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中获取所有钥匙的最短路径
假设我们有一个网格。其中有一些符号。"." 表示空单元格，“#”表示墙壁，“@”表示起点，("a", "b", ...) 全部是钥匙，而 ("A", "B", ...) 全部是锁。我们将从起点开始，每次移动包括向四个方向之一（左、右、上、下）走一步。我们不会走出网格，并且有墙壁阻挡我们的去路。如果我们走过一个钥匙，我们会捡起来。除非我们有相应的钥匙，否则我们不能走过锁。
对于每个像 A、B 等的锁，我们都有像 a、b 等的钥匙，所以锁是大写字母，钥匙是相同的小写字母。
我们必须找到获取所有钥匙的最少移动次数。如果不可能，则返回 -1。
因此，如果输入类似 ["@.a.#","###.#","b.A.B"]，则输出将为 8
为了解决这个问题，我们将遵循以下步骤：
n := 行数，m := 列数
定义一个大小为 3 的数组 start
cnt := 0
初始化 i := 0，当 i < n 时，更新（i 增加 1），执行：
初始化 j := 0，当 j < m 时，更新（j 增加 1），执行：
如果 grid[i, j] 等于 '@'，则：
start[1] := i，start[2] := j
如果 grid[i, j] >= 'a' 且 grid[i, j] <= 'f'，则：
cnt := cnt 和 grid[i, j] - 'a' + 1 的最大值
定义一个集合 visited
req := 2^(cnt - 1)
定义一个数组队列 q
将 start 插入到 q 中
将 start 插入到 visited 中
level := 0
当 (q 不为空) 时，执行：
sz := q 的大小
当 sz 不为零时，每次迭代后减少 sz，执行：
定义一个数组 curr := q 的第一个元素
从 q 中删除元素
key := curr[0]
如果 key 等于 req，则：
返回 level
x := curr[1]，y := curr[2]
prevKey := key
初始化 i := 0，当 i < 4 时，更新（i 增加 1），执行：
nx := x + dir[i, 0]，ny := y + dir[i, 1]
key := prevKey
如果 nx >= 0 且 ny >= 0 且 nx < n 且 ny < m，则：
如果 grid[nx, ny] 等于 '#'，则：
忽略以下部分，跳到下一轮迭代
如果 grid[nx, ny] >= 'a' 且 grid[nx, ny] <= 'f'，则：
key := key OR (2^(grid[nx, ny] - 'a' 的 ASCII 码))
如果 grid[nx, ny] >= 'A' 且 grid[nx, ny] <= 'F'，则：
如果 (将 key 右移 (grid[nx, ny] - 'A' 的 ASCII 码) 次 AND 1) 等于 0，则：
忽略以下部分，跳到下一轮迭代
定义一个数组 state({ key, nx, ny })
如果 state 在 visited 中，则：
忽略以下部分，跳到下一轮迭代
将 state 插入到 q 中
将 state 插入到 visited 中
（level 增加 1）
返回 -1
让我们看看以下实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
int shortestPathAllKeys(vector<string>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<int> start(3);
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '@') {
start[1] = i;
start[2] = j;
}
if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
cnt = max(cnt, grid[i][j] - 'a' + 1);
}
}
}
set<vector<int> > visited;
int req = (1 << cnt) - 1;
queue<vector<int> > q;
q.push(start);
visited.insert(start);
int level = 0;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
vector<int> curr = q.front();
q.pop();
int key = curr[0];
if (key == req)
return level;
int x = curr[1];
int y = curr[2];
int nx, ny;
int prevKey = key;
for (int i = 0; i < 4; i++) {
nx = x + dir[i][0];
ny = y + dir[i][1];
key = prevKey;
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (grid[nx][ny] == '#')
continue;
if (grid[nx][ny] >= 'a' && grid[nx][ny] <=
'f') {
key |= (1 << (grid[nx][ny] - 'a'));
}
if (grid[nx][ny] >= 'A' && grid[nx][ny] <=
'F') {
if (((key >> (grid[nx][ny] - 'A')) & 1)
== 0)
continue;
}
vector<int> state({ key, nx, ny });
if (visited.count(state))
continue;
q.push(state);
visited.insert(state);
}
}
}
level++;
}
return -1;
}
};
main(){
Solution ob;
vector<string> v = {"@.a.#","###.#","b.A.B"};
cout << (ob.shortestPathAllKeys(v));
}输入
{"@.a.#","###.#","b.A.B"}输出
8
508 次查看
