网格图中最少访问的格子数

6353. 网格图中最少访问的格子数

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。

请你返回到达 右下角 格子 (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⁵
1 <= m * n <= 10⁵
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumVisitedCells(vector<vector<int>>& grid) { } };

rust 解法, 执行用时: 75 ms, 内存消耗: 13.7 MB, 提交时间: 2024-03-22 09:52:10

use std::collections::BinaryHeap;

impl Solution {
    pub fn minimum_visited_cells(grid: Vec<Vec<i32>>) -> i32 {
        let mut col_heaps: Vec<BinaryHeap<(i32, usize)>> = vec![BinaryHeap::new(); grid[0].len()]; // 每一列的最小堆
        let mut row_h: BinaryHeap<(i32, usize)> = BinaryHeap::new(); // 行最小堆
        let mut f = 0;
        for (i, row) in grid.iter().enumerate() {
            row_h.clear();
            for (j, &g) in row.iter().enumerate() {
                while !row_h.is_empty() && row_h.peek().unwrap().1 < j {
                    row_h.pop();
                }
                let col_h = &mut col_heaps[j];
                while !col_h.is_empty() && col_h.peek().unwrap().1 < i {
                    col_h.pop();
                }

                f = if i > 0 || j > 0 { i32::MAX } else { 1 }; // 起点算 1 个格子
                if let Some(&(fr, _)) = row_h.peek() {
                    f = -fr + 1; // 从左边跳过来
                }
                if let Some(&(fc, _)) = col_h.peek() {
                    f = f.min(-fc + 1); // 从上边跳过来
                }

                if g > 0 && f < i32::MAX {
                    // f 加负号变成最小堆
                    row_h.push((-f, g as usize + j)); // 经过的格子数，向右最远能到达的列号
                    col_h.push((-f, g as usize + i)); // 经过的格子数，向下最远能到达的行号
                }
            }
        }
        // 此时的 f 是在 (m-1, n-1) 处算出来的
        if f < i32::MAX { f } else { -1 }
    }
}

rust 解法, 执行用时: 59 ms, 内存消耗: 14 MB, 提交时间: 2024-03-22 09:51:48

impl Solution {
    pub fn minimum_visited_cells(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut mn = 0;
        let mut col_stacks: Vec<Vec<(i32, usize)>> = vec![vec![]; n]; // 每列的单调栈
        let mut row_st: Vec<(i32, usize)> = Vec::new(); // 行单调栈
        for (i, row) in grid.iter().enumerate().rev() {
            row_st.clear();
            for (j, &g) in row.iter().enumerate().rev() {
                let col_st = &mut col_stacks[j];
                mn = if i < m - 1 || j < n - 1 { i32::MAX } else { 1 };
                if g > 0 { // 可以向右/向下跳
                    let g = g as usize;
                    // 在单调栈上二分查找最优转移来源
                    let k = row_st.partition_point(|(_, idx)| *idx > j + g);
                    if k < row_st.len() {
                        mn = row_st[k].0 + 1;
                    }
                    let k = col_st.partition_point(|(_, idx)| *idx > i + g);
                    if k < col_st.len() {
                        mn = mn.min(col_st[k].0 + 1);
                    }
                }
                if mn < i32::MAX {
                    // 插入单调栈
                    while !row_st.is_empty() && mn <= row_st.last().unwrap().0 {
                        row_st.pop();
                    }
                    row_st.push((mn, j));
                    while !col_st.is_empty() && mn <= col_st.last().unwrap().0 {
                        col_st.pop();
                    }
                    col_st.push((mn, i));
                }
            }
        }
        // 最后一个算出的 mn 就是 f[0][0]
        if mn < i32::MAX { mn } else { -1 }
    }
}

python3 解法, 执行用时: 1588 ms, 内存消耗: 67.5 MB, 提交时间: 2023-04-11 09:51:35

# m + n 个优先队列
class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dist = [[-1] * n for _ in range(m)]
        dist[0][0] = 1
        row, col = [[] for _ in range(m)], [[] for _ in range(n)]

        def update(x: int, y: int) -> int:
            return y if x == -1 or x > y else x
        
        for i in range(m):
            for j in range(n):
                while row[i] and row[i][0][1] + grid[i][row[i][0][1]] < j:
                    heapq.heappop(row[i])
                if row[i]:
                    dist[i][j] = update(dist[i][j], dist[i][row[i][0][1]] + 1)

                while col[j] and col[j][0][1] + grid[col[j][0][1]][j] < i:
                    heapq.heappop(col[j])
                if col[j]:
                    dist[i][j] = update(dist[i][j], dist[col[j][0][1]][j] + 1)

                if dist[i][j] != -1:
                    heapq.heappush(row[i], (dist[i][j], j))
                    heapq.heappush(col[j], (dist[i][j], i))

        return dist[m - 1][n - 1]

golang 解法, 执行用时: 272 ms, 内存消耗: 18.9 MB, 提交时间: 2023-04-11 09:50:53

func minimumVisitedCells(grid [][]int) (mn int) {
	m, n := len(grid), len(grid[0])
	type pair struct{ x, i int }
	colSt := make([][]pair, n) // 每列的单调栈
	for i := m - 1; i >= 0; i-- {
		st := []pair{} // 当前行的单调栈
		for j := n - 1; j >= 0; j-- {
			st2 := colSt[j]
			mn = math.MaxInt
			if i == m-1 && j == n-1 { // 特殊情况：已经是终点
				mn = 0
			} else if g := grid[i][j]; g > 0 {
				// 在单调栈上二分
				k := j + g
				k = sort.Search(len(st), func(i int) bool { return st[i].i <= k })
				if k < len(st) {
					mn = min(mn, st[k].x)
				}
				k = i + g
				k = sort.Search(len(st2), func(i int) bool { return st2[i].i <= k })
				if k < len(st2) {
					mn = min(mn, st2[k].x)
				}
			}

			if mn < math.MaxInt {
				mn++ // 加上 (i,j) 这个格子
				// 插入单调栈
				for len(st) > 0 && mn <= st[len(st)-1].x {
					st = st[:len(st)-1]
				}
				st = append(st, pair{mn, j})
				for len(st2) > 0 && mn <= st2[len(st2)-1].x {
					st2 = st2[:len(st2)-1]
				}
				colSt[j] = append(st2, pair{mn, i})
			}
		}
	}
	// 最后一个算出的 mn 就是 f[0][0]
	if mn == math.MaxInt {
		return -1
	}
	return
}

func min(a, b int) int { if b < a { return b }; return a }

java 解法, 执行用时: 77 ms, 内存消耗: 69.8 MB, 提交时间: 2023-04-11 09:50:37

class Solution {
    public int minimumVisitedCells(int[][] grid) {
        int m = grid.length, n = grid[0].length, mn = 0;
        List<int[]>[] colSt = new ArrayList[n]; // 每列的单调栈
        Arrays.setAll(colSt, e -> new ArrayList<int[]>());
        for (int i = m - 1; i >= 0; --i) {
            var st = new ArrayList<int[]>(); // 当前行的单调栈
            for (int j = n - 1; j >= 0; --j) {
                var st2 = colSt[j];
                mn = Integer.MAX_VALUE;
                int g = grid[i][j];
                if (i == m - 1 && j == n - 1) // 特殊情况：已经是终点
                    mn = 0;
                else if (g > 0) {
                    // 在单调栈上二分
                    int k = search(st, j + g);
                    if (k < st.size()) mn = Math.min(mn, st.get(k)[0]);
                    k = search(st2, i + g);
                    if (k < st2.size()) mn = Math.min(mn, st2.get(k)[0]);
                }
                if (mn == Integer.MAX_VALUE) continue;

                ++mn; // 加上 (i,j) 这个格子
                // 插入单调栈
                while (!st.isEmpty() && mn <= st.get(st.size() - 1)[0])
                    st.remove(st.size() - 1);
                st.add(new int[]{mn, j});
                while (!st2.isEmpty() && mn <= st2.get(st2.size() - 1)[0])
                    st2.remove(st2.size() - 1);
                st2.add(new int[]{mn, i});
            }
        }
        return mn < Integer.MAX_VALUE ? mn : -1;
    }

    // 见 https://www.bilibili.com/video/BV1AP41137w7/
    private int search(List<int[]> st, int target) {
        int left = -1, right = st.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            int mid = (left + right) >>> 1;
            if (st.get(mid)[1] > target) left = mid; // 范围缩小到 (mid, right)
            else right = mid; // 范围缩小到 (left, mid)
        }
        return right;
    }
}

python3 解法, 执行用时: 1512 ms, 内存消耗: 47.3 MB, 提交时间: 2023-04-11 09:50:14

# dp + 单调栈二分优化
class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        col_st = [[] for _ in range(n)]  # 每列的单调栈
        for i in range(m - 1, -1, -1):
            st = []  # 当前行的单调栈
            for j in range(n - 1, -1, -1):
                st2 = col_st[j]
                mn = inf
                g = grid[i][j]
                if i == m - 1 and j == n - 1:  # 特殊情况：已经是终点
                    mn = 0
                elif g:
                    # 在单调栈上二分
                    k = bisect_left(st, -(j + g), key=lambda p: p[1])
                    if k < len(st): mn = min(mn, st[k][0])
                    k = bisect_left(st2, -(i + g), key=lambda p: p[1])
                    if k < len(st2): mn = min(mn, st2[k][0])
                if mn == inf: continue

                mn += 1  # 加上 (i,j) 这个格子
                # 插入单调栈
                while st and mn <= st[-1][0]:
                    st.pop()
                st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left
                while st2 and mn <= st2[-1][0]:
                    st2.pop()
                st2.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left
        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]

上一题

下一题

详情