Editorial: LeetCode 1293 Shortest Path in a Grid With Obstacles Elimination
https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ from Google
Solutions:
1. BFS with one additional dimension
When being asked about shortest path, think about BFS. The only thing to notice here is that there’s one more variable: the number of the obstacles we eliminate. This means that we need somewhere to store and use this information. One way is to create a data structure to store {row id, col id, obstacles}, and we BFS on this data structure. The other way is to run the BFS on {row id, col id} like we always do, and then have another array to store the obstacles.
One most important thing when writing DFS and BFS is to not visit the same place. We use the obstacles array to avoid that. The only chance we revisite a grid is when we eliminate less obstacles than before. Although the steps to this grid must be longer than before, but since we only eliminate less obstacles, we still have a better chance to reach the destination.
Finally, we need to check if next move is in boundry and if the number of obstacles we eliminate is less than before like we say above.
1class Solution {
2public:
3 typedef pair<int, int> pii;
4 int shortestPath(vector<vector<int>>& grid, int k) {
5 queue<pii> q;
6 int R = grid.size(), C = grid[0].size();
7 vector<vector<int>> dp(R, vector<int>(C, k+1));
8 q.push({0, 0});
9 dp[0][0] = 0;
10 int steps = 0;
11 vector<int> dirs = {1,0,-1,0,1};
12 while (q.size()) {
13 int sz = q.size();
14 while (sz--) {
15 auto [x, y] = q.front(); q.pop();
16 int e = dp[x][y]; // eliminates
17 if (x == (R-1) and y == (C-1)) return steps;
18 for (int i=0; i<4; i++) {
19 int nx = x + dirs[i], ny = y + dirs[i+1];
20 if (nx>=0 and nx<R and ny>=0 and ny<C) {
21 int cost = grid[nx][ny] == 1 ? 1 : 0; // cost can be grid[nx][ny] directly
22 int ne = e + cost;
23 if (ne < dp[nx][ny]) {
24 dp[nx][ny] = ne;
25 q.push({nx, ny});
26 }
27 }
28 }
29 }
30 steps++;
31 }
32 return -1;
33 }
34};
Time complexity: O(RCk). Space complexity: O(R*C)