在C ++中获取所有键的最短路径
对于像A，B等的每个锁，我们都有像a，b等的键，因此锁在大写字母中是相同的字母，而在小写字母中则相同。
让我们看下面的实现以更好地理解-
示例
#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