| comments | difficulty | edit_url | rating | source | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2137 |
第 295 场周赛 Q4 |
|
给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：
0表示一个 空 单元格，1表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。
示例 1：
输入：grid = [[0,1,1],[1,1,0],[1,1,0]] 输出：2 解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。 可以证明我们至少需要移除两个障碍物，所以返回 2 。 注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。
示例 2：
输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] 输出：0 解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j]为0或1grid[0][0] == grid[m - 1][n - 1] == 0
本题实际上也是最短路模型，只不过求解的是移除障碍物的最小数目。
在一个边权只有
如果某条边权值为
$0$ ，那么新拓展出的节点权值就和当前队首节点权值相同，显然可以作为下一次拓展的起点。
时间复杂度
相似题目：
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque([(0, 0, 0)])
vis = set()
dirs = (-1, 0, 1, 0, -1)
while 1:
i, j, k = q.popleft()
if i == m - 1 and j == n - 1:
return k
if (i, j) in vis:
continue
vis.add((i, j))
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if grid[x][y] == 0:
q.appendleft((x, y, k))
else:
q.append((x, y, k + 1))class Solution {
public int minimumObstacles(int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {0, 0, 0});
int[] dirs = {-1, 0, 1, 0, -1};
boolean[][] vis = new boolean[m][n];
while (true) {
var p = q.poll();
int i = p[0], j = p[1], k = p[2];
if (i == m - 1 && j == n - 1) {
return k;
}
if (vis[i][j]) {
continue;
}
vis[i][j] = true;
for (int h = 0; h < 4; ++h) {
int x = i + dirs[h], y = j + dirs[h + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (grid[x][y] == 0) {
q.offerFirst(new int[] {x, y, k});
} else {
q.offerLast(new int[] {x, y, k + 1});
}
}
}
}
}
}class Solution {
public:
int minimumObstacles(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
deque<tuple<int, int, int>> q{{0, 0, 0}};
bool vis[m][n];
memset(vis, 0, sizeof vis);
int dirs[5] = {-1, 0, 1, 0, -1};
while (1) {
auto [i, j, k] = q.front();
q.pop_front();
if (i == m - 1 && j == n - 1) {
return k;
}
if (vis[i][j]) {
continue;
}
vis[i][j] = true;
for (int h = 0; h < 4; ++h) {
int x = i + dirs[h], y = j + dirs[h + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (grid[x][y] == 0) {
q.push_front({x, y, k});
} else {
q.push_back({x, y, k + 1});
}
}
}
}
}
};func minimumObstacles(grid [][]int) int {
m, n := len(grid), len(grid[0])
q := doublylinkedlist.New()
type tuple struct{ i, j, k int }
q.Add(tuple{0, 0, 0})
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := [5]int{-1, 0, 1, 0, -1}
for {
v, _ := q.Get(0)
p := v.(tuple)
q.Remove(0)
i, j, k := p.i, p.j, p.k
if i == m-1 && j == n-1 {
return k
}
if vis[i][j] {
continue
}
vis[i][j] = true
for h := 0; h < 4; h++ {
x, y := i+dirs[h], j+dirs[h+1]
if x >= 0 && x < m && y >= 0 && y < n {
if grid[x][y] == 0 {
q.Insert(0, tuple{x, y, k})
} else {
q.Add(tuple{x, y, k + 1})
}
}
}
}
}function minimumObstacles(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
const dirs = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
let ans = Array.from({ length: m }, v => new Array(n).fill(Infinity));
ans[0][0] = 0;
let deque = [[0, 0]];
while (deque.length) {
let [x, y] = deque.shift();
for (let [dx, dy] of dirs) {
let [i, j] = [x + dx, y + dy];
if (i < 0 || i > m - 1 || j < 0 || j > n - 1) continue;
const cost = grid[i][j];
if (ans[x][y] + cost >= ans[i][j]) continue;
ans[i][j] = ans[x][y] + cost;
deque.push([i, j]);
}
}
return ans[m - 1][n - 1];
}