leetcode1102 得分最高的路径

本文主要是介绍leetcode1102 得分最高的路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://leetcode-cn.com/problems/path-with-maximum-minimum-value/
BFS，从头逐步的向尾部扩展。用一个大堆来存储当前遍历到的点（优先队列）。保证优先去遍历哪些数值大的点。队列中记录的是点的位置，和到当前点的路径中的最小值。
这样走到尾部的时候，取出的点就是最终答案。

public class demo02 {
    int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};

    public int path(int[][] A){
        int n = A.length;
        int m = A[0].length;

        boolean[][] visited = new boolean[n][m];

        Queue<int[]> pq = new PriorityQueue<>((a,b) -> (b[2] - a[2]));
        pq.offer(new int[]{0,0,A[0][0]});

        while(!pq.isEmpty()){
            int[] cell = pq.poll();
            int row = cell[0];
            int col = cell[1];
            if(row == n-1 && col == m-1){
                return cell[2];
            }
            visited[row][col] = true;
            for(int[] dic : directions){
                int nextRow = row + dic[0];
                int nextCol = col + dic[1];
                if(nextRow<0 || nextRow>=n || nextCol<0 || nextCol>=m || visited[nextRow][nextCol]){
                    continue;
                }
                pq.offer(new int[]{nextRow,nextCol,Math.min(cell[2],A[nextRow][nextCol])});
            }
            return -1;
        }
    }
}

这篇关于leetcode1102 得分最高的路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！