Question

1293. 网格中的最短路径

English Version

题目描述

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1 。

 

示例 1：

输入： grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

示例 2：

输入：grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
输出：-1
解释：我们至少需要消除两个障碍才能找到这样的路径。

 

提示：

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] 是 0 或 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
}