推 Che31128: 大師 09/16 23:51
推 nozomizo: 大師 09/16 23:51
→ wwndbk: 昨天怎麼沒有 09/16 23:56
→ wwndbk: 我寫到timeout 救我大師 09/16 23:56
https://leetcode.com/problems/path-with-minimum-effort/description
1631. Path With Minimum Effort
給你一個陣列 heights[][]，heights[i][j] 表示座標位置(i,j)的高度，兩個格子之間
的Effort被定義為兩個點的 heights 絕對值差，你可以往上下左右移動，求出從(0,0)
移動到最右下角的一個路徑，這個路徑途中的所有 Effort 都取最大，返回最小的路徑
Effort。
思路：
1.因為路徑可以往四個方向移動所以我們用BFS去處理確保可以獲得所有解。
2.先用一個 efforts[][] 紀錄到達這個格子的時候，該路徑的最小Effort，初始化
為一個很大的值，efforts[0][0] = 0。
3.把(0,0)推入 Queue 開始 BFS，往四個方向前進，下個點的 Effort 等於:
MAX(當前點和下個點的絕對值差, 當前點的Effort)，如果下個點的Effort不能使
efforts[i][j] 變的更小就不更新，否則把下個點加入Queue繼續BFS。
Java Code:
-----------------------------------------------
class Solution {
public int minimumEffortPath(int[][] heights) {
int n = heights.length;
int m = heights[0].length;
int[][] efforts = new int[n][m];
for (int[] arr : efforts) {
Arrays.fill(arr, Integer.MAX_VALUE);
}
efforts[0][0] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!queue.isEmpty()) {
int[] point = queue.poll();
for (int[] dir : dirs) {
int y = point[0] + dir[0];
int x = point[1] + dir[1];
if (y < 0 || x < 0 || y == n || x == m) continue;
int effort = Math.max(efforts[point[0]][point[1]],
Math.abs(heights[y][x] - heights[point[0]][point[1]]));
if (effort < efforts[y][x]) {
efforts[y][x] = effort;
queue.offer(new int[]{y, x});
}
}
}
return efforts[n - 1][m - 1];
}
}
-----------------------------------------------
--
https://i.imgur.com/sjdGOE3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1694879473.A.DC2.html