-
Notifications
You must be signed in to change notification settings - Fork 0
/
1631_Path_With_Minimum_Effort.java
67 lines (51 loc) · 1.48 KB
/
1631_Path_With_Minimum_Effort.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
1631. Path With Minimum Effort
Difficulty: Medium
1631_Path_With_Minimum_Effort.java
*/
class T {
public int i;
public int j;
public int d;
public T(int i, int j, int d) {
this.i = i;
this.j = j;
this.d = d;
}
}
class Solution {
public int minimumEffortPath(int[][] heights) {
final int m = heights.length;
final int n = heights[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.d - b.d);
int[][] diff = new int[m][n];
Arrays.stream(diff).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
boolean[][] seen = new boolean[m][n];
minHeap.offer(new T(0, 0, 0));
diff[0][0] = 0;
while (!minHeap.isEmpty()) {
final int i = minHeap.peek().i;
final int j = minHeap.peek().j;
final int d = minHeap.poll().d;
if (i == m - 1 && j == n - 1)
return d;
seen[i][j] = true;
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y])
continue;
final int newDiff = Math.abs(heights[i][j] - heights[x][y]);
final int maxDiff = Math.max(diff[i][j], newDiff);
if (diff[x][y] > maxDiff) {
diff[x][y] = maxDiff;
minHeap.offer(new T(x, y, maxDiff));
}
}
}
throw new IllegalArgumentException();
}
}