LeetCode 1631. 最小体力消耗路径
原题链接
中等
作者:
我不叫喂
,
2023-12-11 17:22:09
,
所有人可见
,
阅读 50
今日的每日一题,纯用的BFS,一年前学的算法基础课终于发挥了用处
import java.util.*;
class Solution {
static int dx[] = new int[]{1, -1, 0, 0};
static int dy[] = new int[]{0, 0, 1, -1};
public static int minimumEffortPath(int[][] heights) {
int arr[][] = new int[heights.length][heights[0].length];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
arr[i][j] = Integer.MAX_VALUE;
}
}
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{0, 0});
arr[0][0] = 0;
while (!queue.isEmpty()) {
int t[] = queue.poll();
for (int i = 0; i < 4; i++) {
int x = t[0] + dx[i];
int y = t[1] + dy[i];
if (x >= 0 && x < heights.length && y >= 0 && y < heights[0].length) {
int ans = Math.max(Math.abs(heights[x][y] - heights[t[0]][t[1]]), arr[t[0]][t[1]]);
if (ans < arr[x][y]) {
arr[x][y] = ans;
queue.add(new int[]{x, y});
}
}
}
}
return arr[heights.length - 1][heights[0].length - 1];
}
}