2577-在网格图中访问一个格子的最少时间

给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。

你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意
一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。

请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。

示例 1：

**输入：** grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
**输出：** 7
**解释：** 一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。

示例 2：

**输入：** grid = [[0,2,4],[3,2,1],[1,0,4]]
**输出：** -1
**解释：** 没法从左上角按题目规定走到右下角。

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 0 <= grid[i][j] <= 105
• grid[0][0] == 0

方法一：Dijkstra 算法

前置知识：Dijkstra 算法

见本题 视频讲解 。

提示 1

如果 grid}[0][1]\le 1 或者 grid}[1][0]\le 1，那么可以通过「反复横跳」来「等待」。否则根本就无法移动到这两个格子，也就无法到达终点，返回 -1。

通过反复横跳，出发时间可以为 0,2,4,\cdots 这些偶数。

提示 2

定义 dis}[i][j] 为到达 (i,j) 的最小时间，那么 dis}[0][0]=0，答案为 dis}[m-1][n-1]。

如果没有别的约束，那么每条边的边权可以视作 1，跑 Dijkstra 算法就可以算出答案。

根据题意，dis}[i][j] 需要至少为 grid}[i][j]；且根据网格图的性质，在可以反复横跳的情况下，到达一个格子的时间的奇偶性是不变的，那么 dis}[i][j] 应当与 i+j 的奇偶性相同。

证明：想象成国际象棋的棋盘（两种颜色），每走一步，颜色一定会改变，所以走了偶数步之后一定会落在相同颜色的格子上，奇数步会落在另一个颜色的格子上。这些颜色相同的格子的奇偶性是相同的，可以用坐标之和的奇偶性表示。

算上这两个约束，才能计算出正确的结果。

[sol2-Python3]

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:  # 无法「等待」
            return -1

        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = 0
        h = [(0, 0, 0)]
        while True:  # 可以等待，就一定可以到达终点
            d, i, j = heappop(h)
            if d > dis[i][j]: continue
            if i == m - 1 and j == n - 1:  # 找到终点，此时 d 一定是最短路
                return d
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子
                if 0 <= x < m and 0 <= y < n:
                    nd = max(d + 1, grid[x][y])
                    nd += (nd - x - y) % 2  # nd 必须和 x+y 同奇偶
                    if nd < dis[x][y]:
                        dis[x][y] = nd  # 更新最短路
                        heappush(h, (nd, x, y))

[sol2-Java]

class Solution {
    private final static int[][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        var dis = new int[m][n];
        for (int i = 0; i < m; ++i)
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        dis[0][0] = 0;
        var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0, 0});
        for (;;) { // 可以等待，就一定可以到达终点
            var p = pq.poll();
            int d = p[0], i = p[1], j = p[2];
            if (d > dis[i][j]) continue;
            if (i == m - 1 && j == n - 1) // 找到终点，此时 d 一定是最短路
                return d;
            for (var q : DIRS) { // 枚举周围四个格子
                int x = i + q[0], y = j + q[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int nd = Math.max(d + 1, grid[x][y]);
                    nd += (nd - x - y) % 2; // nd 必须和 x+y 同奇偶
                    if (nd < dis[x][y]) {
                        dis[x][y] = nd; // 更新最短路
                        pq.add(new int[]{nd, x, y});
                    }
                }
            }
        }
    }
}

[sol2-C++]

class Solution {
    static constexpr int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public:
    int minimumTime(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        int dis[m][n];
        memset(dis, 0x3f, sizeof(dis));
        dis[0][0] = 0;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, 0, 0);
        for (;;) { // 可以等待，就一定可以到达终点
            auto[d, i, j] = pq.top();
            pq.pop();
            if (d > dis[i][j]) continue;
            if (i == m - 1 && j == n - 1) // 找到终点，此时 d 一定是最短路
                return d;
            for (auto &q : dirs) { // 枚举周围四个格子
                int x = i + q[0], y = j + q[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int nd = max(d + 1, grid[x][y]);
                    nd += (nd - x - y) % 2; // nd 必须和 x+y 同奇偶
                    if (nd < dis[x][y]) {
                        dis[x][y] = nd; // 更新最短路
                        pq.emplace(nd, x, y);
                    }
                }
            }
        }
    }
};

[sol2-Go]

var dirs = []struct{ x, y int }{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

func minimumTime(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if grid[0][1] > 1 && grid[1][0] > 1 { // 无法「等待」
		return -1
	}

	dis := make([][]int, m)
	for i := range dis {
		dis[i] = make([]int, n)
		for j := range dis[i] {
			dis[i][j] = math.MaxInt
		}
	}
	dis[0][0] = 0
	h := &hp{ {} }
	for { // 可以等待，就一定可以到达终点
		p := heap.Pop(h).(tuple)
		d, i, j := p.d, p.i, p.j
		if d > dis[i][j] {
			continue
		}
		if i == m-1 && j == n-1 { // 找到终点，此时 d 一定是最短路
			return d
		}
		for _, q := range dirs { // 枚举周围四个格子
			x, y := i+q.x, j+q.y
			if 0 <= x && x < m && 0 <= y && y < n {
				nd := max(d+1, grid[x][y])
				nd += (nd - x - y) % 2 // nd 必须和 x+y 同奇偶
				if nd < dis[x][y] {
					dis[x][y] = nd // 更新最短路
					heap.Push(h, tuple{nd, x, y})
				}
			}
		}
	}
}

type tuple struct{ d, i, j int }
type hp []tuple
func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].d < h[j].d }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(tuple)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func max(a, b int) int { if a < b { return b }; return a }

复杂度分析

• 时间复杂度：O(mn\log mn)，其中 m 和 n 分别为 grid 的行数和列数。
• 空间复杂度：O(mn)。

方法二：二分答案 + BFS

前置知识：二分

见【基础算法精讲 04】 。

提示 1

先不管「反复横跳」的事，假设在时刻 endTime 到达终点，那么我们从终点出发，一刻不停地反向到达起点。

如果可以从终点到达起点，说明可以在大于 endTime 的时刻到达终点；反之，如果无法从终点到达起点，说明无法在小于 endTime 的时刻到达终点。

有单调性，可以二分到达终点的时间。

提示 2

根据方法一中的思路，如果最后答案与 m+n 的奇偶性不同，则加一调整一下。

[sol1-Python3]

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:  # 无法「等待」
            return -1

        vis = [[-inf] * n for _ in range(m)]
        def check(end_time: int) -> bool:
            vis[-1][-1] = end_time
            q = [(m - 1, n - 1)]
            t = end_time - 1
            while q:
                tmp = q
                q = []
                for i, j in tmp:
                    for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):  # 枚举周围四个格子
                        if 0 <= x < m and 0 <= y < n and vis[x][y] != end_time and grid[x][y] <= t:
                            if x == 0 and y == 0: return True
                            vis[x][y] = end_time  # 用二分的值来标记，避免重复创建 vis 数组
                            q.append((x, y))
                t -= 1
            return False

        left = max(grid[-1][-1], m + n - 2) - 1
        right = max(map(max, grid)) + m + n  # 开区间
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid): right = mid
            else: left = mid
        return right + (right - m - n) % 2

[sol1-Java]

class Solution {
    private final static int[][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    private int[][] grid, vis;

    public int minimumTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        this.grid = grid;
        vis = new int[m][n];
        int left = Math.max(grid[m - 1][n - 1], m + n - 2) - 1;
        int right = (int) 1e5 + m + n; // 开区间
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid)) right = mid;
            else left = mid;
        }
        return right + (right + m + n) % 2;
    }

    private boolean check(int endTime) {
        int m = grid.length, n = grid[0].length;
        vis[m - 1][n - 1] = endTime;
        var q = new ArrayList<int[]>();
        q.add(new int[]{m - 1, n - 1});
        for (int t = endTime - 1; !q.isEmpty(); --t) {
            var tmp = q;
            q = new ArrayList<>();
            for (var p : tmp) {
                int i = p[0], j = p[1];
                for (var d : DIRS) { // 枚举周围四个格子
                    int x = i + d[0], y = j + d[1];
                    if (0 <= x && x < m && 0 <= y && y < n && vis[x][y] != endTime && grid[x][y] <= t) {
                        if (x == 0 && y == 0) return true;
                        vis[x][y] = endTime; // 用二分的值来标记，避免重复创建 vis 数组
                        q.add(new int[]{x, y});
                    }
                }
            }
        }
        return false;
    }
}

[sol1-C++]

class Solution {
    static constexpr int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public:
    int minimumTime(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        if (grid[0][1] > 1 && grid[1][0] > 1) // 无法「等待」
            return -1;

        int vis[m][n]; memset(vis, -1, sizeof(vis));
        auto check = [&](int end_time) -> bool {
            vis[m - 1][n - 1] = end_time;
            vector<pair<int, int>> q = { {m - 1, n - 1} };
            for (int t = end_time - 1; !q.empty(); --t) {
                vector<pair<int, int>> nxt;
                for (auto &[i, j] : q) {
                    for (auto &d : dirs) { // 枚举周围四个格子
                        int x = i + d[0], y = j + d[1];
                        if (0 <= x && x < m && 0 <= y && y < n && vis[x][y] != end_time && grid[x][y] <= t) {
                            if (x == 0 && y == 0) return true;
                            vis[x][y] = end_time; // 用二分的值来标记，避免重复创建 vis 数组
                            nxt.emplace_back(x, y);
                        }
                    }
                }
                q = move(nxt);
            }
            return false;
        };

        int left = max(grid.back().back(), m + n - 2) - 1, right = 1e5 + m + n; // 开区间
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right + (right + m + n) % 2;
    }
};

[sol1-Go]

type pair struct{ x, y int }
var dirs = []pair{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

func minimumTime(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	if grid[0][1] > 1 && grid[1][0] > 1 { // 无法「等待」
		return -1
	}

	vis := make([][]int, m)
	for i := range vis {
		vis[i] = make([]int, n)
	}
	endTime := sort.Search(1e5+m+n, func(endTime int) bool {
		if endTime < grid[m-1][n-1] || endTime < m+n-2 {
			return false
		}
		vis[m-1][n-1] = endTime
		q := []pair{ {m - 1, n - 1} }
		for t := endTime - 1; len(q) > 0; t-- {
			tmp := q
			q = nil
			for _, p := range tmp {
				for _, d := range dirs { // 枚举周围四个格子
					x, y := p.x+d.x, p.y+d.y
					if 0 <= x && x < m && 0 <= y && y < n && vis[x][y] != endTime && grid[x][y] <= t {
						if x == 0 && y == 0 {
							return true
						}
						vis[x][y] = endTime // 用二分的值来标记，避免重复创建 vis 数组
						q = append(q, pair{x, y})
					}
				}
			}
		}
		return false
	})
	return endTime + (endTime+m+n)%2
}

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

复杂度分析

• 时间复杂度：O(mn\log U)，其中 m 和 n 分别为 grid 的行数和列数，U 为 grid}[i][j] 的最大值。
• 空间复杂度：O(mn)。

相似题目

• 778. 水位上升的泳池中游泳