0778. Swim in Rising Water

题目信息

题号:

0778

难度:

Hard

主题:

矩阵、路径可达性、最早时间

原题:

LeetCode 0778

重点:

时间 t 同时是水位,只有高度不超过 t 的格子才能进入;移动限于四方向相邻格,返回从左上角到右下角首次连通的最小时间

题目重述

给定一个 n x n 整数矩阵 grid,其中 grid[i][j] 表示格子 (i,j) 的高度。下雨后水位随时间上升,在时间 t 时水位恰好为 t。

你从左上角 (0,0) 出发。只有当当前格和目标相邻格的高度都不超过 t 时,才能在它们之间游动;移动只允许上、下、左、右四个方向,且游动本身不消耗时间。

请返回能够到达右下角 (n - 1,n - 1) 的最小时间。1 <= n <= 50,所有高度互不相同,并满足 0 <= grid[i][j] < n^2。

自建示例

较低路径绕开高峰:

输入:grid = [[0,7,2],[1,8,3],[6,5,4]]
输出:6
解释:时间 6 时可以沿 0 -> 1 -> 6 -> 5 -> 4 到达右下角,路径上的最高高度为 6。时间小于 6 时,起点一侧无法越过高度 6、7 或 8 的格子到达终点,因此最早时间为 6。

网格只有起点一个格子:

输入:grid = [[0]]
输出:0
解释:当 ``n = 1`` 时,左上角同时就是右下角。起点高度为 0,在时间 0 已经位于目标位置,无需等待或移动。