LeetCode-1293. Shortest Path in a Grid with Obstacles Elimination

LeetCode-1293. Shortest Path in a Grid with Obstacles Elimination

Given a ​​m * n​​​ grid, where each cell is either ​​0​​​ (empty) or ​​1​​ (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner ​​(0, 0)​​​ to the lower right corner ​​(m-1, n-1)​​ given that you can eliminate at most ​​k​​ obstacles. If it is not possible to find such walk return -1.

Example 1:

Input: grid = [[0,0,0],  [1,1,0], [0,0,0],  [0,1,1], [0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10.  The shortest path with one obstacle elimination at position (3,2) is 6. Such path is ​​(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2)​​.

Example 2:

Input: grid = [[0,1,1], [1,1,1], [1,0,0]], k = 1Output: -1Explanation: We need to eliminate at least two obstacles to find such a walk.

Constraints:

​​grid.length == m​​​​grid[0].length == n​​​​1 <= m, n <= 40​​​​1 <= k <= m*n​​​​grid[i][j] == 0 or 1​​​​grid[0][0] == grid[m-1][n-1] == 0​​

题解：

需要使用cut数组和visit数组来进行剪枝，cut[i]判断每次到达i位置的最小转换次数，如果当前次数大于最小值，那么进行剪枝。visit[i][j]判断经过j次转换到达i是否访问过。

坐标存储使用压缩存储。

class Solution {public: int shortestPath(vector>& grid, int k) { int m = grid.size(), n = grid[0].size(); int next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector> visit(1600, vector(k + 1, false)); vector cut(1600, INT_MAX); queue> q; q.push({0, 0}); visit[0][0] = true; int res = 0; while (q.empty() == false) { int cnt = q.size(); while (cnt > 0) { auto t = q.front(); q.pop(); int x = t.first / n, y = t.first % n; if (x == m - 1 && y == n - 1) { return res; } for (int i = 0; i < 4; i++) { int nx = x + next[i][0], ny = y + next[i][1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n) { int tmpk = t.second + grid[nx][ny]; int tmpd = nx * n + ny; if (tmpk <= k && tmpk < cut[tmpd] && visit[tmpd][tmpk] == false) { q.push({tmpd, tmpk}); visit[tmpd][tmpk] = true; cut[tmpd] = tmpk; } } } cnt--; } res++; } return -1; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。