给你一个 R 行 C 列的整数矩阵 A。矩阵上的路径从 00 开始在 R-1C-1 结束。路径沿四个基本方向上、下、左、右展开从一个已访问单元格移动到任一相邻的未访问单元格。路径的得分是该路径上的 最小 值。例如路径 8 → 4 → 5 → 9 的值为 4 。找出所有路径中得分 最高 的那条路径返回其 得分。

可以使用动态规划来解决这个问题。我们定义 dp[i][j] 表示从起点到 (i,j) 的路径中的最小值。则转移方程为：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i+1][j], dp[i][j+1], A[i][j])

其中 A[i][j] 是矩阵中 (i,j) 位置的值。注意边界条件，当 i=0 或 j=0 或 i=R-1 或 j=C-1 时，对应的 dp[i][j] 只需要考虑与其相邻的格子。

最后，我们遍历所有的 dp[i][j]，找到其中的最大值即可。时间复杂度为 O(RC)。具体实现如下：

class Solution { public: int maximumMinimumPath(vector<vector>& A) { int R = A.size(), C = A[0].size(); vector<vector> dp(R, vector(C, 0)); dp[0][0] = A[0][0]; for (int i = 1; i < R; i++) { dp[i][0] = min(dp[i-1][0], A[i][0]); } for (int j = 1; j < C; j++) { dp[0][j] = min(dp[0][j-1], A[0][j]); } for (int i = 1; i < R; i++) { for (int j = 1; j < C; j++) { if (i == R-1 && j == C-1) { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } else { dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), min(dp[i+1][j], dp[i][j+1])); dp[i][j] = min(dp[i][j], A[i][j]); } } } return dp[R-1][C-1]; } }