代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
You are given an m x n
integer matrix grid
where each cell is either 0
(empty) or 1
(obstacle). You can move up, down, left, or right from and to an empty cell in one step.
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 = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 40
1 <= k <= m * n
grid[i][j]
is either 0
or 1
.grid[0][0] == grid[m - 1][n - 1] == 0
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 3:
return m + n - 2
q = deque([(0, 0, k)])
vis = {(0, 0, k)}
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j, k = q.popleft()
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if x == m - 1 and y == n - 1:
return ans
if grid[x][y] == 0 and (x, y, k) not in vis:
q.append((x, y, k))
vis.add((x, y, k))
if grid[x][y] == 1 and k > 0 and (x, y, k - 1) not in vis:
q.append((x, y, k - 1))
vis.add((x, y, k - 1))
return -1
class Solution {
public int shortestPath(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
if (k >= m + n - 3) {
return m + n - 2;
}
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {0, 0, k});
boolean[][][] vis = new boolean[m][n][k + 1];
vis[0][0][k] = true;
int ans = 0;
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
int[] p = q.poll();
k = p[2];
for (int j = 0; j < 4; ++j) {
int x = p[0] + dirs[j];
int y = p[1] + dirs[j + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (x == m - 1 && y == n - 1) {
return ans;
}
if (grid[x][y] == 0 && !vis[x][y][k]) {
q.offer(new int[] {x, y, k});
vis[x][y][k] = true;
} else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) {
q.offer(new int[] {x, y, k - 1});
vis[x][y][k - 1] = true;
}
}
}
}
}
return -1;
}
}
class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
if (k >= m + n - 3) return m + n - 2;
queue<vector<int>> q;
q.push({0, 0, k});
vector<vector<vector<bool>>> vis(m, vector<vector<bool>>(n, vector<bool>(k + 1)));
vis[0][0][k] = true;
int ans = 0;
vector<int> dirs = {-1, 0, 1, 0, -1};
while (!q.empty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
auto p = q.front();
k = p[2];
q.pop();
for (int j = 0; j < 4; ++j) {
int x = p[0] + dirs[j], y = p[1] + dirs[j + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (x == m - 1 && y == n - 1) return ans;
if (grid[x][y] == 0 && !vis[x][y][k]) {
q.push({x, y, k});
vis[x][y][k] = true;
} else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) {
q.push({x, y, k - 1});
vis[x][y][k - 1] = true;
}
}
}
}
}
return -1;
}
};
func shortestPath(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
if k >= m+n-3 {
return m + n - 2
}
q := [][]int{[]int{0, 0, k}}
vis := make([][][]bool, m)
for i := range vis {
vis[i] = make([][]bool, n)
for j := range vis[i] {
vis[i][j] = make([]bool, k+1)
}
}
vis[0][0][k] = true
dirs := []int{-1, 0, 1, 0, -1}
ans := 0
for len(q) > 0 {
ans++
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
k = p[2]
for j := 0; j < 4; j++ {
x, y := p[0]+dirs[j], p[1]+dirs[j+1]
if x >= 0 && x < m && y >= 0 && y < n {
if x == m-1 && y == n-1 {
return ans
}
if grid[x][y] == 0 && !vis[x][y][k] {
q = append(q, []int{x, y, k})
vis[x][y][k] = true
} else if grid[x][y] == 1 && k > 0 && !vis[x][y][k-1] {
q = append(q, []int{x, y, k - 1})
vis[x][y][k-1] = true
}
}
}
}
}
return -1
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。