1102. 得分最高的路径

题目描述

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

输入：[[5,4,5],[1,2,6],[7,4,6]]
输出：4
解释：
得分最高的路径用黄色突出显示。

解决方案

BFS+优先队列

class Solution {
public:
    struct Point {
        int x;
        int y;
        int val;

        Point(int x, int y, int val) {
            this->x=x;
            this->y=y;
            this->val=val;
        }

        bool operator < (const struct Point &rhs) const {
            return val > rhs.val;
        }
    };

    int maximumMinimumPath(vector<vector<int>>& grid) {
        int r=grid.size();
        int c=grid[0].size();
        int ans=grid[0][0];
        vector<vector<int>> direction{{-1,0},{0,1},{1,0},{0,-1}};
        priority_queue<Point> q;
        vector<vector<int>> visited(r, vector<int>(c, false));

        q.emplace(0,0,grid[0][0]);
        visited[0][0]= true;
        while (!q.empty()) {
            auto item=q.top();
            q.pop();
            ans=min(ans,item.val);
            if (item.x==r-1&&item.y==c-1) {
                return ans;
            }
            for (auto offset:direction) {
                int x=item.x+offset[0];
                int y=item.y+offset[1];
                if (x>=0&&x<r&&y>=0&&y<c&&!visited[x][y]) {
                    q.emplace(x,y,grid[x][y]);
                    visited[x][y]= true;
                }
            }
        }

        return ans;
    }
};