题解 | #牛群的最小体力消耗值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型二维数组 
     * @return int整型
     */
    public int minimumEffortPath (int[][] heights) {
        // write code here
        /**
        相邻牛之间的高度差绝对值的最大值最小。最短路径问题。使 用 Dijkstra 算法。
         */

        int rows=heights.length;
        int cols=heights[0].length;
        int[][] effort=new int[rows][cols];
        
        for(int[] e:effort){
            Arrays.fill(e,Integer.MAX_VALUE);
        }
        PriorityQueue<int[]> dp=new PriorityQueue<>((a,b)->a[2]-b[2]);
        dp.offer(new int[]{0,0,0});
        int[][] dierctions={{1,0},{-1,0},{0,1},{0,-1}};
        while(!dp.isEmpty()){
            int[] current=dp.poll();
            int row=current[0];
            int col=current[1];
            int currenteffort=current[2];
            if(row==rows-1&&col==cols-1) return currenteffort;
            for(int []dir:dierctions){
                int newrow=row+dir[0];
                int newcol=col+dir[1];
                if(isValid(newrow,newcol,rows,cols)){
                    int neweffort=Math.max(currenteffort,Math.abs(heights[newrow][newcol]-heights[row][col]));
                    if(neweffort<effort[newrow][newcol]){
                        effort[newrow][newcol]=neweffort;
                        dp.offer(new int[]{newrow,newcol,neweffort});
                    }
                }
            }
        }
        return -1;
    }
    private boolean isValid(int newrow,int newcol,int rows,int cols){
        return newrow>=0&&newrow<rows&&newcol>=0&&newcol<cols;
    }
    
}
/**
public int minimumEffortPath (int[][] heights) {
        // write code here
        
        相邻牛之间的高度差绝对值的最大值最小。最短路径问题。使 用 Dijkstra 算法。
        
        int rows=heights.length;
        int cols=heights[0].length;
        PriorityQueue<int[]> dp=new PriorityQueue<>((a,b) -> a[2]-b[2]);
        int[][] effort=new int[rows][cols];
        for (int[] row : effort) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        int[][] direction={{1,0},{-1,0},{0,1},{0,-1}};
        dp.offer(new int[] {0,0,0});
        while(!dp.isEmpty()){
            int[] current=dp.poll();
            int row=current[0];
            int col=current[1];
            int currenteffort=current[2];
            if(row==rows-1&&col==cols-1) return currenteffort;
            for(int[] dir:direction){
                int newrow=row+dir[0];
                int newcol=col+dir[1];
                if(isValid(newrow,newcol,rows,cols)){
                    int neweffort=Math.max(currenteffort,Math.abs(heights[newrow][newcol]-heights[row][col]));
                    if(neweffort<effort[newrow][newcol]){
                        effort[newrow][newcol]=neweffort;
                        dp.offer(new int[]{newrow,newcol,neweffort});
                    }
                }
            }
        }
        return -1;
    }
    private boolean isValid(int row,int col,int rows,int cols){
        return row>=0&&col>=0&&row<rows&&col<cols;
    } */