Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The cost of a route is its largest single step, not the sum.
  2. 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