你準備參加一場遠足活動。給你一個二維 rows x columns 的地圖 heights ，其中 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] 連續(xù)格子的差值絕對值最大為 2 。
這條路徑比路徑 [1,2,2,2,5] 更優(yōu)，因為另一條路徑差值最大值為 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 i=0;i<fa.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){x=find(x);y=find(y);if(x==y) return;fa[x]=y;}public int minimumEffortPath(int[][] heights) {PriorityQueue<edge> priorityQueue=new PriorityQueue<>((o1, o2) -> o1.len-o2.len);int r=heights.length,c=heights[0].length;for(int i=0;i<r;i++)//將相鄰的格子高度差作為邊的權(quán)重for(int j=0;j<c;j++){int cur=i*c+j;if(i<r-1){priorityQueue.add(new edge(cur,cur+c, Math.abs(heights[i][j]-heights[i+1][j])));}if(j<c-1){priorityQueue.add(new edge(cur,cur+1, Math.abs(heights[i][j]-heights[i][j+1])));}}fa=new int[r*c];init();while (!priorityQueue.isEmpty())//不斷的加入權(quán)重小的邊，直到起點和終點連通{edge cur=priorityQueue.poll();union(cur.x,cur.x1);if(find(0)==find(r*c-1))return cur.len;}return 0;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 1631. 最小体力消耗路径（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。