1293. Shortest Path in a Grid with Obstacles Elimination
有一个 m * n 的迷宫，
grid[x][y] = 1 代表座标 (x, y) 是墙壁
目标是从 (0, 0) 走到 (m-1, n-1)
但可以选择消除最多 k 个墙壁
问所需的最短路径
一开始有点卡住，偷点Hint 知道要用 BFS 才知道怎么做 :(
可以想像成有 k+1 层的立体迷宫
只能在平面移动，不过遇到墙壁的话会被往上拉一层
超过 k 层就会失败
终点会是 (m-1, n-1, 0), (m-1, n-1, 1), ..., (m-1, n-1, k)
不过直接做会 TLE，我改成判断对于 (x, y, r)
如果已经走过 (x, y, r'), r' < r 的话就停止
加上这个剪枝才过的
class Solution {
public:
using Pos = array<int, 3>;
int shortestPath(vector<vector<int>>& grid, int k) {
int seen[41][41];
memset(seen, 0xff, sizeof seen); // fill with -1
int m = grid.size();
int n = grid[0].size();
queue<Pos> Q;
Q.push({0, 0, k});
for (int ans = 0; ans < m * n; ans++) {
int s = Q.size();
for (int i = 0; i < s; i++) {
auto [x, y, p] = Q.front();
Q.pop();
if (x < 0 || x > m - 1) continue;
if (y < 0 || y > n - 1) continue;
if (grid[x][y]) p -= 1;
if (p < 0) continue;
if (x == m - 1 && y == n - 1)
return ans;
if (seen[x][y] >= p) continue;
seen[x][y] = p;
Q.push({x-1, y, p});
Q.push({x+1, y, p});
Q.push({x, y-1, p});
Q.push({x, y+1, p});
}
}
return -1;
}
};
因为前后修修改改，所以写起来有点丑