1631. 最小体力消耗路径(1948)

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

1
2
3
4
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

1
2
3
输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

1
2
3
输入：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]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 10^6

二分+dfs：属于最小化最大值问题

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
class Solution {
    int dirs[] = {0, 1, 0, -1, 0};
    int res = Integer.MAX_VALUE;
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        int l = 0, r = (int)1e6;
        while (l < r) {
            int mid = l + r >>> 1;
            int vis[][] = new int[m][n];
            if (dfs(0, 0, heights, vis, mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    public boolean dfs(int x, int y, int[][] heights, int vis[][], int threshold) {
        int m = heights.length, n = heights[0].length;
        if (x == m-1 && y == n-1) return true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i], ny = y + dirs[i+1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (vis[nx][ny] == 1) continue;
            if (Math.abs(heights[nx][ny]-heights[x][y]) > threshold) continue;
            vis[x][y] = 1;
            boolean res = dfs(nx, ny, heights, vis, threshold);
            // vis[x][y] = 0;  // 不要设置回0，vis为1说明这个点之后的所有情况都判断过了
            if (res) return true;
        }
        return false;
    }
}

SPFA算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length, dis[][] = new int[m][n];
        for (int t[] : dis) Arrays.fill(t, Integer.MAX_VALUE);
        dis[0][0] = 0;
        Deque<int[]> dq = new LinkedList<>();  // 普通队列
        dq.offer(new int[]{0, 0, 0});
        int dirs[] = {0, 1, 0, -1, 0};
        while (!dq.isEmpty()) {
            int p[] = dq.poll();
            int x = p[0], y = p[1], c = p[2];
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i], ny = y + dirs[i+1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (Math.max(c, Math.abs(heights[nx][ny]-heights[x][y])) < dis[nx][ny]) {
                    dis[nx][ny] = Math.max(c, Math.abs(heights[nx][ny]-heights[x][y]));
                    dq.offer(new int[]{nx, ny, dis[nx][ny]});
                }
            }
        }
        return dis[m-1][n-1];
    }
}

并查集

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
class Solution {    
    int[] pa, rank;
    int count = 0;
    int find(int x) {
        return pa[x] == x ? x : (pa[x] = find(pa[x]));
    }
    void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (rank[fx] <= rank[fy]) pa[fx] = pa[fy];
        else pa[fy] = pa[fx];
        if (rank[fx] == rank[fy]) rank[y]++;
        count++;
    }
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        if (m == 1 && n == 1) return 0;
        pa = new int[m*n];
        Arrays.setAll(pa, i -> i);
        rank = new int[m*n];
        List<int[]> g = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cur = i * n + j;
                // 只需要考虑右下的方向，就可以考虑到所有点的上下左右的连通性
                // 比如说当前点(3,3)，它上面得连通性就由点(2,3)来连通（上面的点的下方向）
                if (i > 0) g.add(new int[]{cur-n, cur, Math.abs(heights[i][j]-heights[i-1][j])});
                if (j > 0) g.add(new int[]{cur-1, cur, Math.abs(heights[i][j]-heights[i][j-1])});
                // 也可以加上左上两个方向，但没必要
                // if (i < m-1) g.add(new int[]{cur+n, cur, Math.abs(heights[i][j]-heights[i+1][j])});
                // if (j < n-1) g.add(new int[]{cur+1, cur, Math.abs(heights[i][j]-heights[i][j+1])});
            }
        }
        g.sort((i, j) -> i[2] - j[2]);
        for (int e[] : g) {
            int last = e[0], cur = e[1], cost = e[2];
            union(last, cur);
            if (find(0) == find(m*n-1)) {
                return cost;
            }
        }
        return -1;
    }
}

dijkstra算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length, dis[][] = new int[m][n];
        for (int t[] : dis) Arrays.fill(t, Integer.MAX_VALUE);
        dis[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> i[2] - j[2]);
        pq.offer(new int[]{0, 0, 0});
        int dirs[] = {0, 1, 0, -1, 0};
        while (!pq.isEmpty()) {
            int p[] = pq.poll();
            int x = p[0], y = p[1], c = p[2];
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i], ny = y + dirs[i+1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (Math.max(c, Math.abs(heights[nx][ny]-heights[x][y])) < dis[nx][ny]) {
                    dis[nx][ny] = Math.max(c, Math.abs(heights[nx][ny]-heights[x][y]));
                    pq.offer(new int[]{nx, ny, dis[nx][ny]});
                }
            }
        }
        return dis[m-1][n-1];
    }
}