题目描述

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).

中文翻译

给定矩阵R行C列,求从(0,0)到(R-1,C-1)各条可能路径中最小值的最大值。

样例

Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: 
The path with the maximum score is highlighted in yellow. 

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

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

算法1

(dijkstra变种) $O(n^2logn)$

和dijkstra类似,只不过优先队列中比较的是路径中的最小值

C++ 代码

class Solution {
public:
   struct Vertex {
      int i;
      int j;
      int val;
      bool operator<(const Vertex& rhs) const { return val < rhs.val; }
   };

   int maximumMinimumPath(vector<vector<int>>& A) {
      const vector<pair<int, int>> dirs = { {0,1},{0,-1},{-1,0},{1,0} };
      const int n = A.size(), m = A[0].size();
      auto vv = vector(n, vector<int>(m, -1));
      priority_queue<Vertex> q;
      q.push({ 0,0,A[0][0] });
      while (!q.empty()) {
         const auto [i, j, val] = q.top(); q.pop();         
         for (auto [dx, dy] : dirs) {
            int x = i + dx, y = j + dy;
            if (x < 0 || x >= n || y < 0 || y >= m || vv[x][y] != -1) continue;
            vv[x][y] = min(val, A[x][y]);
            if (x == n - 1 && y == m - 1) return vv[x][y];
            q.push({ x, y, vv[x][y] });
         }
      }
      return -1;
   }
};