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.from({length: m}, () => new Array(n).fill(Infinity));

    class MinHeap {
        constructor() {
            this.items = [];
        }

        get size() {
            return this.items.length;
        }

        peek() {
            return this.items[0];
        }

        push(item) {
            const items = this.items;
            items.push(item);
            let index = items.length - 1;
            while (index > 0) {
                const parent = Math.floor((index - 1) / 2);
                if (items[parent][0] <= item[0]) break;
                items[index] = items[parent];
                index = parent;
            }
            items[index] = item;
        }

        pop() {
            const items = this.items;
            const root = items[0];
            const last = items.pop();
            if (items.length === 0) return root;

            let index = 0;
            while (true) {
                let child = index * 2 + 1;
                if (child >= items.length) break;
                if (child + 1 < items.length && items[child + 1][0] < items[child][0]) {
                    child++;
                }
                if (items[child][0] >= last[0]) break;
                items[index] = items[child];
                index = child;
            }
            items[index] = last;
            return root;
        }
    }

    const rowHeaps = Array.from({length: m}, () => new MinHeap());
    const colHeaps = Array.from({length: n}, () => new MinHeap());
    dp[0][0] = 1;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            while (rowHeaps[i].size > 0) {
                const [, col] = rowHeaps[i].peek();
                if (col + grid[i][col] >= j) break;
                rowHeaps[i].pop();
            }
            if (rowHeaps[i].size > 0) {
                dp[i][j] = Math.min(dp[i][j], rowHeaps[i].peek()[0] + 1);
            }

            while (colHeaps[j].size > 0) {
                const [, row] = colHeaps[j].peek();
                if (row + grid[row][j] >= i) break;
                colHeaps[j].pop();
            }
            if (colHeaps[j].size > 0) {
                dp[i][j] = Math.min(dp[i][j], colHeaps[j].peek()[0] + 1);
            }

            if (dp[i][j] !== Infinity) {
                rowHeaps[i].push([dp[i][j], j]);
                colHeaps[j].push([dp[i][j], i]);
            }
        }
    }

    return dp[m - 1][n - 1] === Infinity ? -1 : dp[m - 1][n - 1];
};

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

复杂度分析

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

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目