算法训练三十天！
day28
题目一：
1631.最小体力消耗路径
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小** 体力消耗值** 。
这类题目就是很经典的搜索题目。搜索题目主要就是找到状态空间，以及状态转移方向。并且要加上visited，不然的话一个状态可能会重复多次访问，导致复杂度暴增！
这里的状态空间就是每个坐标，并且还需要把对应的值给加上(因为同一个坐标可能有不同的路径到达这，并且可能按照第二次的路径会比第一次更优，所以这种新状态需要重新考虑)
也就是可以用一个数组来存状态情况。
但是可以优化的点是，我们可以用该数组存的值来代替最小值，这样当下一次有状态移动到该点的时候，只需要判断是否值会更小就行了！
综上所述
public int minimumEffortPath(int[][] heights) {
int[][] dirs = new int[][]{
{0, 1}, {0, -1}, {1, 0}, {-1, 0}
};
int n = heights.length;
int m = heights[0].length;
int[][] visited = new int[n][m];
int[][] dp= new int[n][m];
for (int i = 0; i < n; i++) {
Arrays.fill(visited[i], Integer.MAX_VALUE);
Arrays.fill(dp[i], 0);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{0, 0, 0, heights[0][0]});
visited[0][0] = 0;
while (!pq.isEmpty()) {
int[] t = pq.poll();
if(t[1]==n-1&&t[2]==m-1){
return t[0];
}
for (int i = 0; i < 4; i++) {
int x = t[1] + dirs[i][0];
int y = t[2] + dirs[i][1];
if (x >= 0 && x < n && y >= 0 && y < m ) {
int diff = Math.abs(heights[x][y] - t[3]);
int minDiff = Math.max(diff, t[0]);
if(minDiff < visited[x][y]){
pq.add(new int[]{minDiff, x, y, heights[x][y]});
visited[x][y] = minDiff;
}
}
}
}
return -1;
}
评论 (0)
