解题思路
想到最短路径问题,自然想到用BFS解决问题,但是只记录位置还不够,还需要记录当前拥有的钥匙状态。
需要的数据结构
- 钥匙的个数是\(1-6\),用一个二进制数表示钥匙的状态,第\(i\)位表示钥匙已经获取到。
- 队列
q
记录当前位置以及拥有钥匙的状态,(i,j,state)
,\(state\)的第\(i\)位为1表示当前拥有第\(i\)把钥匙。 - 数组
vis
记录当前位置是否被访问,\(vis(i,j,state)\)。
步骤
- 遍历
grid
,找到起点位置,统计钥匙的个数\(k\)。 - 从起点出发,加入队列
q
,并将vis[si][sj][0]
置为\(true\),并判断当前位置是否为终点,即当前位置是否拥有所有的钥匙,即state
的二进制表示中的1的个数是否为k
。如果是,返回当前的步数(队列出队次数)。 - 不是终点,从当前位置出发,往四个方向走,如果可以走到下一个位置\((x,y)\),将\((x,y,next)\)加入队列
q
。 - 队列循环结束,没有找到所有的钥匙,退出循环后返回
-1
。
临界条件
第\(3\)步中的\((x,y)\)需要满足在网格内,如果\((x,y)\)位置是抢,即grid[x][y]=='#'
,或者\((x,y)\)的位置是锁,但当前没有对应的钥匙,即grid[x][y] >= 'A' && grid[x][y] <= 'F' && (state >> (grid[x][y] - 'A') & 1) == 0)
,则不能走到位置\((x,y)\)。
核心代码如下:
class Solution {
public:
const static inline vector<int> dirs = {-1, 0, 1, 0, -1};
int shortestPathAllKeys(vector<string>& grid) {
int m = grid.size(), n = grid[0].size();
int k = 0;
int si = 0, sj = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
char c = grid[i][j];
// 累加钥匙数量
if (islower(c)) ++k;
// 起点
else if (c == '@') si = i, sj = j;
}
}
queue<tuple<int, int, int>> q{{{si, sj, 0}}};
vector<vector<vector<bool>>> vis(m, vector<vector<bool>>(n, vector<bool>(1 << k)));
vis[si][sj][0] = true;
int ans = 0;
while (!q.empty()) {
for (int t = q.size(); t; --t) {
auto [i, j, state] = q.front();
q.pop();
// 找到所有钥匙,返回当前步数
if (state == (1 << k) - 1) return ans;
// 往四个方向搜索
for (int h = 0; h < 4; ++h) {
int x = i + dirs[h], y = j + dirs[h + 1];
// 在边界范围内
if (x >= 0 && x < m && y >= 0 && y < n) {
char c = grid[x][y];
// 是墙,或者是锁,但此时没有对应的钥匙,无法通过
if (c == '#' || (isupper(c) && (state >> (c - 'A') & 1) == 0)) continue;
int nxt = state;
// 是钥匙,更新状态
if (islower(c)) nxt |= 1 << (c - 'a');
// 此状态未访问过,入队
if (!vis[x][y][nxt]) {
vis[x][y][nxt] = true;
q.push({x, y, nxt});
}
}
}
}
// 步数加一
++ans;
}
return -1;
}
};
标签:get,keys,位置,864,int,state,vector,钥匙,grid
From: https://www.cnblogs.com/hql5/p/16877537.html