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 <= 1000 <= A[i][j] <= 10^9
得分最高的路径。
给你一个 R 行 C 列的整数矩阵 A。矩阵上的路径从 [0,0] 开始，在 [R-1,C-1] 结束。
路径沿四个基本方向（上、下、左、右）展开，从一个已访问单元格移动到任一相邻的未访问单元格。
路径的得分是该路径上的 最小 值。例如，路径 8 → 4 → 5 → 9 的值为 4 。
找出所有路径中得分 最高 的那条路径，返回其 得分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-minimum-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路是Dijikstra算法，可以先做1631题。这道题还是在图中找一条路径使得路径的cost最小。1631题所谓的cost最小是路径上任意一条边的权重要尽量小，而边的权重是由两个相邻cell.val之间的差值决定的；而这道题的cost是取这条路径上最小的节点值。我这里还是提供一个BFS为基础的做法，这里同时我们提供一个boolean数组记录matrix上的坐标是否被访问过，这里跟1631题不同的地方在于这道题我们要确保不能重复访问某些cell，因为只要某个cell被访问过了，那么这个位置上的坐标值就会参与决定目标路径的cost。
举个例子，比如当前你扫描过了若干个cell，你目前的cost是5好了。此时你扫描到一个cell，值为10，那么如果这个cell最后是去到终点的必经之路的话，路径的cost就会变成10；但是如果你扫描别的路径的时候又经过这个点但是另一条路径的cost小于10，则不需要扫描这个节点值为10的坐标了，因为如果再次遍历的话，也许另一条也能到达终点的路径的cost就也被改成10了。
时间O(m * n * nlogn)
空间O(mn)
Java实现
1 class Solution {
2 public int maximumMinimumPath(int[][] matrix) {
3 int m = matrix.length;
4 int n = matrix[0].length;
5 boolean[][] visited = new boolean[m][n];
6
7 // cost, row, col
8 PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
9 queue.offer(new int[] { matrix[0][0], 0, 0 });
10 int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
11 while (!queue.isEmpty()) {
12 int[] cur = queue.poll();
13 int cost = cur[0];
14 int row = cur[1];
15 int col = cur[2];
16 if (row == m - 1 && col == n - 1) {
17 return cost;
18 }
19 visited[row][col] = true;
20 for (int[] dir : dirs) {
21 int nextRow = row + dir[0];
22 int nextCol = col + dir[1];
23 if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol] == true) {
24 continue;
25 }
26 queue.offer(new int[] { Math.min(cost, matrix[nextRow][nextCol]), nextRow, nextCol });
27 }
28 }
29 return -1;
30 }
31 }
相关题目
1102. Path With Maximum Minimum Value
1631. Path With Minimum Effort