千套模板快速自助建站,一键 wordpress,wordpress酒店模板下载,在线二维码制作你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights #xff0c;其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) #xff0c;且你希望去最右下角的格子 (rows-1, columns-1) #xff08;注意下标从 0 开始编号其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) 且你希望去最右下角的格子 (rows-1, columns-1) 注意下标从 0 开始编号。你每次可以往 上下左右 四个方向之一移动你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1
输入heights [[1,2,2],[3,8,2],[5,3,5]] 输出2 解释路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。 这条路径比路径 [1,2,2,2,5] 更优因为另一条路径差值最大值为 3 。
代码
class Solution {class edge{int x,x1,len;public edge(int x, int x1, int len) {this.x x;this.x1 x1;this.len len;}}int[] fa;public void init(){for(int i0;ifa.length;i)fa[i]i;}public int find(int x){if(x!fa[x])fa[x]find(fa[x]);return fa[x];}public void union(int x,int y){xfind(x);yfind(y);if(xy) return;fa[x]y;}public int minimumEffortPath(int[][] heights) {PriorityQueueedge priorityQueuenew PriorityQueue((o1, o2) - o1.len-o2.len);int rheights.length,cheights[0].length;for(int i0;ir;i)//将相邻的格子高度差作为边的权重for(int j0;jc;j){int curi*cj;if(ir-1){priorityQueue.add(new edge(cur,curc, Math.abs(heights[i][j]-heights[i1][j])));}if(jc-1){priorityQueue.add(new edge(cur,cur1, Math.abs(heights[i][j]-heights[i][j1])));}}fanew int[r*c];init();while (!priorityQueue.isEmpty())//不断的加入权重小的边直到起点和终点连通{edge curpriorityQueue.poll();union(cur.x,cur.x1);if(find(0)find(r*c-1))return cur.len;}return 0;}
}
