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;
}
};
因為前後修修改改，所以寫起來有點醜