Practice › Graphs
Path With Minimum Effort
Medium · Graphs · Asked at Google, Amazon, Microsoft
You walk from the top-left to the bottom-right cell of a height map, moving up/down/left/right. The effort of a route is the largest absolute height difference between two consecutive cells on it. Print the minimum possible effort.
Input
First line: r c. Next r lines: c heights.
Output
The minimum effort.
Constraints
- 1 ≤ r, c ≤ 100
- 1 ≤ height ≤ 10^6
Dijkstra where a path's cost is the maximum edge so far (not the sum). Binary search on the effort + BFS also works.
Example 1
Input
3 3 1 2 2 3 8 2 5 3 5
Output
2
Example 2
Input
3 3 1 2 3 3 8 4 5 3 5
Output
1
Hints
- The cost of a route is its largest single step, not the sum.
- Dijkstra still works: the "distance" of a cell is the smallest possible maximum step to reach it; extending a route gives max(current, |height difference|).
Approach
Dijkstra on the grid with effort[cell] = best known maximum step. Pop the cell with the smallest effort; for each neighbour, the candidate is max(effort[cell], |h[nb] − h[cell]|); if it improves the neighbour, update and push. When the bottom-right cell is popped, its effort is final. (Binary searching the answer with a BFS also works.)
Complexity: O(r · c · log(r · c)) time · O(r · c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<vector<long long>> h(R, vector<long long>(C));
for (auto &row : h)
for (auto &x : row) cin >> x;
vector<vector<long long>> eff(R, vector<long long>(C, LLONG_MAX));
typedef tuple<long long, int, int> T;
priority_queue<T, vector<T>, greater<T>> pq;
eff[0][0] = 0;
pq.emplace(0, 0, 0);
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while (!pq.empty()) {
long long e;
int x, y;
tie(e, x, y) = pq.top();
pq.pop();
if (e > eff[x][y]) continue;
if (x == R - 1 && y == C - 1) break;
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (a < 0 || b < 0 || a >= R || b >= C) continue;
long long ne = max(e, llabs(h[a][b] - h[x][y]));
if (ne < eff[a][b]) eff[a][b] = ne, pq.emplace(ne, a, b);
}
}
cout << eff[R - 1][C - 1] << "\n";
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
h = [data[2 + i * C : 2 + (i + 1) * C] for i in range(R)]
INF = float("inf")
eff = [[INF] * C for _ in range(R)]
eff[0][0] = 0
pq = [(0, 0, 0)]
while pq:
e, x, y = heapq.heappop(pq)
if e > eff[x][y]:
continue
if x == R - 1 and y == C - 1:
break
for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= a < R and 0 <= b < C:
ne = max(e, abs(h[a][b] - h[x][y]))
if ne < eff[a][b]:
eff[a][b] = ne
heapq.heappush(pq, (ne, a, b))
print(eff[R - 1][C - 1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt(), C = sc.nextInt();
long[][] h = new long[R][C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) h[i][j] = sc.nextLong();
long[][] eff = new long[R][C];
for (long[] row : eff) Arrays.fill(row, Long.MAX_VALUE);
eff[0][0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.add(new long[] {0, 0, 0});
int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
while (!pq.isEmpty()) {
long[] t = pq.poll();
int x = (int) t[1], y = (int) t[2];
if (t[0] > eff[x][y]) continue;
if (x == R - 1 && y == C - 1) break;
for (int k = 0; k < 4; k++) {
int a = x + dx[k], b = y + dy[k];
if (a < 0 || b < 0 || a >= R || b >= C) continue;
long ne = Math.max(t[0], Math.abs(h[a][b] - h[x][y]));
if (ne < eff[a][b]) {
eff[a][b] = ne;
pq.add(new long[] {ne, a, b});
}
}
}
System.out.println(eff[R - 1][C - 1]);
}
}Solve Path With Minimum Effort online · All practice problems