Hard

题目描述

给你一个 m x n 的整数矩阵 grid ，其中每个单元格不是 0（空）就是 1（障碍物）。你可以在一步内从一个空单元格移动到相邻的任一空单元格（上、下、左、右）。

返回从左上角 (0, 0) 走到右下角 (m - 1, n - 1) 的最少步数，给定你可以消除最多 k 个障碍物。如果无法找到这样的路径，返回 -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
解释：我们至少需要消除两个障碍物才能找到这样的路径。

约束条件：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 40
  • 1 <= k <= m * n
  • grid[i][j] 不是 0 就是 1
  • grid[0][0] == grid[m - 1][n - 1] == 0

解题思路

这是一个带状态的最短路径问题，需要使用三维BFS来解决。

核心思路： 传统的BFS只记录位置 (x, y)，但这里需要额外记录"剩余可消除障碍物的次数"，因此状态变为三维：(x, y, remain_k)。

算法步骤：

  1. 使用队列进行BFS，队列中存储 (row, col, remaining_eliminations, steps)
  2. 使用三维visited数组 visited[row][col][k] 避免重复访问相同状态
  3. 对每个位置的四个方向进行探索：
    • 如果下一个位置是空地(0)，直接移动，消除次数不变
    • 如果下一个位置是障碍物(1)，需要消耗一次消除机会才能通过
  4. 当到达终点时，返回当前步数
  5. 如果队列为空仍未到达终点，返回-1

优化点：

  • 当 k >= m + n - 3 时，可以直接走曼哈顿距离（因为足够消除路径上所有障碍物）
  • 使用三维visited数组避免状态重复

代码实现

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        
        // 如果k足够大，可以直接走曼哈顿距离
        if (k >= m + n - 3) {
            return m + n - 2;
        }
        
        vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));
        queue<vector<int>> q; // {row, col, remaining_k, steps}
        q.push({0, 0, k, 0});
        visited[0][0][k] = true;
        
        vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            
            int row = curr[0], col = curr[1], remain = curr[2], steps = curr[3];
            
            if (row == m - 1 && col == n - 1) {
                return steps;
            }
            
            for (auto& dir : dirs) {
                int newRow = row + dir[0], newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    int newRemain = remain - grid[newRow][newCol];
                    
                    if (newRemain >= 0 && !visited[newRow][newCol][newRemain]) {
                        visited[newRow][newCol][newRemain] = true;
                        q.push({newRow, newCol, newRemain, steps + 1});
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        
        # 如果k足够大，可以直接走曼哈顿距离
        if k >= m + n - 3:
            return m + n - 2
            
        visited = set()
        queue = deque([(0, 0, k, 0)])  # (row, col, remaining_k, steps)
        visited.add((0, 0, k))
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while queue:
            row, col, remain, steps = queue.popleft()
            
            if row == m - 1 and col == n - 1:
                return steps
                
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                
                if 0 <= new_row < m and 0 <= new_col < n:
                    new_remain = remain - grid[new_row][new_col]
                    
                    if new_remain >= 0 and (new_row, new_col, new_remain) not in visited:
                        visited.add((new_row, new_col, new_remain))
                        queue.append((new_row, new_col, new_remain, steps + 1))
        
        return -1

public class Solution {
    public int ShortestPath(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        
        // 如果k足够大，可以直接走曼哈顿距离
        if (k >= m + n - 3) {
            return m + n - 2;
        }
        
        bool[,,] visited = new bool[m, n, k + 1];
        Queue<int[]> queue = new Queue<int[]>();
        queue.Enqueue(new int[] {0, 0, k, 0}); // {row, col, remaining_k, steps}
        visited[0, 0, k] = true;
        
        int[][] dirs = new int[][] {
            new int[] {0, 1}, new int[] {1, 0}, 
            new int[] {0, -1}, new int[] {-1, 0}
        };
        
        while (queue.Count > 0) {
            int[] curr = queue.Dequeue();
            int row = curr[0], col = curr[1], remain = curr[2], steps = curr[3];
            
            if (row == m - 1 && col == n - 1) {
                return steps;
            }
            
            foreach (int[] dir in dirs) {
                int newRow = row + dir[0], newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    int newRemain = remain - grid[newRow][newCol];
                    
                    if (newRemain >= 0 && !visited[newRow, newCol, newRemain]) {
                        visited[newRow, newCol, newRemain] = true;
                        queue.Enqueue(new int[] {newRow, newCol, newRemain, steps + 1});
                    }
                }
            }
        }
        
        return -1;
    }
}

var shortestPath = function(grid, k) {
    const m = grid.length;
    const n = grid[0].length;
    
    if (m === 1 && n === 1) return 0;
    
    const queue = [[0, 0, k, 0]]; // [row, col, remaining_k, steps]
    const visited = new Set();
    visited.add(`0,0,${k}`);
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (queue.length > 0) {
        const [row, col, remainingK, steps] = queue.shift();
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n) {
                continue;
            }
            
            const newRemainingK = remainingK - grid[newRow][newCol];
            
            if (newRemainingK < 0) {
                continue;
            }
            
            if (newRow === m - 1 && newCol === n - 1) {
                return steps + 1;
            }
            
            const state = `${newRow},${newCol},${newRemainingK}`;
            if (!visited.has(state)) {
                visited.add(state);
                queue.push([newRow, newCol, newRemainingK, steps + 1]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n × k)，其中每个状态 (i, j, remain_k) 最多被访问一次
空间复杂度O(m × n × k)，visited数组和队列的空间开销

相关题目