Given a matrix of integers
A
with
R
rows and
C
columns, find the
maximum
score of a path starting at
[0,0]
and ending at
[R-1,C-1]
.
The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.
A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).
Example 1:
Input: [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow.
Example 2:
Input:
[[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Example 3:
Input:
[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3
Note:
-
1 <= R, C <= 100 -
0 <= A[i][j] <= 10^9
1、题目描述¶
给你一个 R 行 C 列的整数矩阵 A。矩阵上的路径从 [0,0] 开始，在 [R-1,C-1] 结束。
路径沿四个基本方向（上、下、左、右）展开，从一个已访问单元格移动到任一相邻的未访问单元格。
路径的得分是该路径上的 最小 值。例如，路径 8 → 4 → 5 → 9 的值为 4 。
找出所有路径中得分 最高 的那条路径，返回其 得分。
示例 1：
输入：[[5,4,5],[1,2,6],[7,4,6]] 输出：4 解释： 得分最高的路径用黄色突出显示。
示例 2：
输入：[[2,2,1,2,2,2],[1,2,2,2,1,2]] 输出：2
示例 3：
输入：[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]] 输出：3
提示：
- 1 <= R, C <= 100
- 0 <= A[i][j] <= 10^9