資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
