[LeetCode] 1102. Path With Maximum Minimum Value

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

得分最高的路径。

给你一个 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 }