1102. Path With Maximum Minimum Value

Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.

The score of a path is the minimum value in that path.

• For example, the score of the path 8 → 4 → 5 → 9 is 4.

c++

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
        vector<vector<int>> dp(n, vector<int>(m, -1));
        dp[0][0] = grid[0][0];
        
        priority_queue<array<int,3>> q;
        q.push({grid[0][0], 0,0});
        while(!q.empty()) {
            auto [val, y, x] = q.top(); q.pop();
            if(y == n - 1 and x == m - 1) return val;
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                    int v = min(dp[y][x], grid[ny][nx]);
                    if(v > dp[ny][nx]) {
                        q.push({v, ny,nx});
                        dp[ny][nx] = v;
                    }
                }
            }
        }
        
        return dp[n-1][m-1];
    }
};