2617. 网格中到达目标的最少访问单元格数

Hard

题目描述

给定一个 0 索引的 m x n 整数矩阵 grid。你的初始位置在左上角单元格 (0, 0)。

从单元格 (i, j) 开始，你可以移动到以下单元格之一：

单元格 (i, k)，其中 j < k <= grid[i][j] + j（向右移动），或
单元格 (k, j)，其中 i < k <= grid[i][j] + i（向下移动）。

返回到达右下角单元格 (m - 1, n - 1) 所需访问的最少单元格数。如果没有有效路径，返回 -1。

示例 1：

输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
输出：4
解释：上图显示了恰好访问 4 个单元格的路径之一。

示例 2：

输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
输出：3
解释：上图显示了恰好访问 3 个单元格的路径之一。

示例 3：

输入：grid = [[2,1,0],[1,0,0]]
输出：-1
解释：可以证明不存在路径。

约束：

m == grid.length
n == grid[i].length
1 <= m, n <= 10^5
1 <= m * n <= 10^5
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0

解题思路

这是一个在网格中寻找最短路径的问题，需要用到动态规划和优先队列优化。

核心思路：

使用 dp[i][j] 表示到达位置 (i,j) 的最少步数
对于每个位置 (i,j)，我们需要找到所有能到达它的前驱位置
一个位置 (x,y) 能到达 (i,j) 当且仅当：
- x == i 且 y < j 且 y + grid[x][y] >= j（同行向右）
- 或 y == j 且 x < i 且 x + grid[x][y] >= i（同列向下）

优化策略： 为了避免 O(mn) 的暴力搜索，我们使用两个优先队列：

rowPQ[i]：存储第 i 行中所有可能作为前驱的位置信息
colPQ[j]：存储第 j 列中所有可能作为前驱的位置信息

对于每个位置 (i,j)，我们从对应的行和列优先队列中取出最优解，然后清理过期的位置（无法到达当前位置的位置）。

算法流程：

初始化 dp[0][0] = 1
按行优先顺序遍历每个位置
对于位置 (i,j)，从行队列和列队列中找最小步数
更新当前位置的步数，并将其加入对应队列
返回 dp[m-1][n-1]

代码实现

class Solution {
public:
    int minimumVisitedCells(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        
        // Priority queues for each row and column
        vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> rowPQ(m);
        vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> colPQ(n);
        
        dp[0][0] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Get minimum from row priority queue
                while (!rowPQ[i].empty() && rowPQ[i].top().second + grid[i][rowPQ[i].top().second] < j) {
                    rowPQ[i].pop();
                }
                if (!rowPQ[i].empty()) {
                    dp[i][j] = min(dp[i][j], rowPQ[i].top().first + 1);
                }
                
                // Get minimum from column priority queue
                while (!colPQ[j].empty() && colPQ[j].top().second + grid[colPQ[j].top().second][j] < i) {
                    colPQ[j].pop();
                }
                if (!colPQ[j].empty()) {
                    dp[i][j] = min(dp[i][j], colPQ[j].top().first + 1);
                }
                
                // Add current cell to priority queues if reachable
                if (dp[i][j] != INT_MAX) {
                    rowPQ[i].push({dp[i][j], j});
                    colPQ[j].push({dp[i][j], i});
                }
            }
        }
        
        return dp[m-1][n-1] == INT_MAX ? -1 : dp[m-1][n-1];
    }
};

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        import heapq
        
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        
        # Priority queues for each row and column
        rowPQ = [[] for _ in range(m)]
        colPQ = [[] for _ in range(n)]
        
        dp[0][0] = 1
        
        for i in range(m):
            for j in range(n):
                # Get minimum from row priority queue
                while rowPQ[i] and rowPQ[i][0][1] + grid[i][rowPQ[i][0][1]] < j:
                    heapq.heappop(rowPQ[i])
                if rowPQ[i]:
                    dp[i][j] = min(dp[i][j], rowPQ[i][0][0] + 1)
                
                # Get minimum from column priority queue
                while colPQ[j] and colPQ[j][0][1] + grid[colPQ[j][0][1]][j] < i:
                    heapq.heappop(colPQ[j])
                if colPQ[j]:
                    dp[i][j] = min(dp[i][j], colPQ[j][0][0] + 1)
                
                # Add current cell to priority queues if reachable
                if dp[i][j] != float('inf'):
                    heapq.heappush(rowPQ[i], (dp[i][j], j))
                    heapq.heappush(colPQ[j], (dp[i][j], i))
        
        return dp[m-1][n-1] if dp[m-1][n-1] != float('inf') else -1

public class Solution {
    public int MinimumVisitedCells(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,] dp = new int[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        
        // Priority queues for each row and column
        var rowPQ = new PriorityQueue<(int steps, int col), int>[m];
        var colPQ = new PriorityQueue<(int steps, int row), int>[n];
        
        for (int i = 0; i < m; i++) {
            rowPQ[i] = new PriorityQueue<(int, int), int>();
        }
        for (int j = 0; j < n; j++) {
            colPQ[j] = new PriorityQueue<(int, int), int>();
        }
        
        dp[0, 0] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Get minimum from row priority queue
                while (rowPQ[i].Count > 0 && rowPQ[i].Peek().col + grid[i][rowPQ[i].Peek().col] < j) {
                    rowPQ[i].Dequeue();
                }
                if (rowPQ[i].Count > 0) {
                    dp[i, j] = Math.Min(dp[i, j], rowPQ[i].Peek().steps + 1);
                }
                
                // Get minimum from column priority queue
                while (colPQ[j].Count > 0 && colPQ[j].Peek().row + grid[colPQ[j].Peek().row][j] < i) {
                    colPQ[j].Dequeue();
                }
                if (colPQ[j].Count > 0) {
                    dp[i, j] = Math.Min(dp[i, j], colPQ[j].Peek().steps + 1);
                }
                
                // Add current cell to priority queues if reachable
                if (dp[i, j] != int.MaxValue) {
                    rowPQ[i].Enqueue((dp[i, j], j), dp[i, j]);
                    colPQ[j].Enqueue((dp[i, j], i), dp[i, j]);
                }
            }
        }
        
        return dp[m-1, n-1] == int.MaxValue ? -1 : dp[m-1, n-1];
    }
}

var minimumVisitedCells = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dp = Array(m).fill().map(() => Array(n).fill(Infinity));
    
    // Priority queues for each row and column
    const rowPQ = Array(m).fill().map(() => []);
    const colPQ = Array(n).fill().map(() => []);
    
    // Helper function to maintain min heap
    const heapPush = (heap, item) => {
        heap.push(item);
        heap.sort((a, b) => a[0] - b[0]);
    };
    
    const heapPop = (heap) => {
        return heap.shift();
    };
    
    dp[0][0] = 1;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Get minimum from row priority queue
            while (rowPQ[i].length > 0 && rowPQ[i][0][1] + grid[i][rowPQ[i][0][1]] < j) {
                heapPop(rowPQ[i]);
            }
            if (rowPQ[i].length > 0) {
                dp[i][j] = Math.min(dp[i][j], rowPQ[i][0][0] + 1);
            }
            
            // Get minimum from column priority queue
            while (colPQ[j].length > 0 && colPQ[j][0][1] + grid[colPQ[j][0][1]][j] < i) {
                heapPop(colPQ[j]);
            }
            if (colPQ[j].length > 0) {
                dp[i][j] = Math.min(dp[i][j], colPQ[j][0][0] + 1);
            }
            
            // Add current cell to priority queues if reachable
            if (dp[i][j] !== Infinity) {
                heapPush(rowPQ[i], [dp[i][j], j]);
                heapPush(colPQ[j], [dp[i][j], i]);
            }
        }
    }
    
    return dp[m-1][n-1]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	值	说明
时间复杂度	O(mn log(mn))	每个位置最多被加入和移除优先队列一次，每次操作 O(log(mn))
空间复杂度	O(mn)	dp 数组和优先队列的空间

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目