You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.
class Solution {
private static class Node {
int weight, r, c;
Node(int r, int c, int weight) {
this.weight = weight;
this.r = r;
this.c = c;
}
}
private static int[] dr = new int[]{1, 0, 0, -1};
private static int[] dc = new int[]{0, 1, -1, 0};
private int[][] graph;
// Dijkstra
public int minimumEffortPath(int[][] heights) {
this.graph = heights;
PriorityQueue<Node> pq = new PriorityQueue<>((n1,n2) -> Integer.compare(n1.weight, n2.weight));
pq.offer(new Node(0, 0, 0));
Set<String> visited = new HashSet<>();
while (!pq.isEmpty()) {
Node curr = pq.poll();
if (!visited.add(curr.r + "," + curr.c)) {
// skip duplicated nodes, since these nodes
// are not optimal results
continue;
}
if (curr.r == graph.length - 1 && curr.c == graph[0].length - 1) {
return curr.weight;
}
for (int i = 0; i < 4; ++i) {
int newR = curr.r + dr[i];
int newC = curr.c + dc[i];
if (!isValid(newR, newC)) {
continue;
}
int newWeight = Math.max(curr.weight, Math.abs(graph[curr.r][curr.c] - graph[newR][newC]));
pq.offer(new Node(newR, newC, newWeight));
}
}
// shouldn't reach here, as we can walk to right lower corner anyway
return -1;
}
private boolean isValid(int r, int c) {
if (r < 0 || r >= graph.length) return false;
if (c < 0 || c >= graph[0].length) return false;
return true;
}
}
class Solution {
public int minimumEffortPath(int[][] heights) {
int left = 0, right = 1e6;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (bfsCheck(heights, mid)) {
right = mid;
} else {
left = mid;
}
}
if (bfsCheck(heights, left)) return left;
else return right;
}
private boolean bfsCheck(int[][] graph, int maxDiff) {
int[] dr = new int[] {0, 1, 0, -1};
int[] dc = new int[] {1, 0, -1, 0};
Deque<int[]> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.offerFirst(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] curr = queue.pollLast();
int r = curr[0], c = curr[1];
String key = r + "," + c;
if (!visited.add(key)) {
continue;
}
if (r == graph.length - 1 && c == graph[0].length - 1) {
return true;
}
for (int i = 0; i < 4; ++i) {
int newR = r + dr[i];
int newC = c + dc[i];
if (!isValid(graph, newR, newC)) {
continue;
}
int diff = Math.abs(graph[r][c] - graph[newR][newC]);
if (diff <= maxDiff) {
queue.offerFirst(new int[] {newR, newC});
}
}
}
return false;
}
private boolean isValid(int[][] graph, int r, int c) {
if (r < 0 || r >= graph.length) return false;
if (c < 0 || c >= graph[0].length) return false;
return true;
}
}
