最小体力消耗路径

发表于
本文字数： 6.8k 阅读时长 ≈ 6 分钟

LeetCode每日一题，973. Path With Minimum Effort

先看题目描述

yCvvo8.png

大意就是给定一个二维矩阵，让我们返回从左上角走到右下角的最小体力消耗路径的值，消耗体力的定义是路径上相邻山的高度差的最大值

算法和思路

这题不会，看题解才明白的

我们可以将本题抽象成如下的一个图论模型：

  • 我们将地图中的每一个格子看成图中的一个节点；

  • 我么将两个相邻（左右相邻或者上下相邻）的两个格子对应的节点之间连接一条无向边，边的权值为这两个格子的高度差的绝对值；

  • 我们需要找到一条从左上角到右下角的最短路径，其中一条路径的长度定义为其经过的所有边权的最大值。

二分查找

我们可以将这个问题转化成一个「判定性」问题，即：

是否存在一条从左上角到右下角的路径，其经过的所有边权的最大值不超过 x？

这个判定性问题解决起来并不复杂，我们只要从左上角开始进行深度优先搜索或者广度优先搜索，在搜索的过程中只允许经过边权不超过 x 的边，搜索结束后判断是否能到达右下角即可

由于格子的高度范围为 [1,1000000]，因此我们可以在 [0,1000000] 的范围内对 x 进行二分查找。在每一步查找的过程中，我们使用深度优先搜索或者广度优先搜索判断是否可以从左上角到达右下角，并根据判定结果更新二分查找的左边界或右边界即可

并查集

我们将这 mn 个节点放入并查集中，实时维护它们的连通性

由于我们需要找到从左上角到右下角的最短路径，因此我们可以将图中的所有边按照权值从小到大进行排序，并依次加入并查集中。当我们加入一条权值为 x 的边之后，如果左上角和右下角从非连通状态变为连通状态，那么 x 即为答案

算法源码

二分查找

下面的代码使用的是深度优先搜索

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
class Solution {
    final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] visited;
        int left = 0;
        int right = 1000000;
        while (left <= right) {
            int mid = (left + right) / 2;
            visited = new boolean[m][n];
            dfs(0, 0, mid, heights, visited);
            if (visited[m - 1][n - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private void dfs(int x, int y, int mid,int[][] heights, boolean[][] visited) {
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + DIRECTIONS[i][0];
            int ny = y + DIRECTIONS[i][1];
            if (nx >= 0 && nx < heights.length && ny >= 0 && ny < heights[0].length && !visited[nx][ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                dfs(nx, ny, mid, heights, visited);
            }
        }
    }
}

下面的代码使用的是广度优先搜索

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
class Solution {
    final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] visited;
        int left = 0;
        int right = 1000000;
        while (left <= right) {
            int mid = (left + right) / 2;
            visited = new boolean[m][n];
            Queue<int[]> queue = new ArrayDeque<>();
            queue.offer(new int[]{0, 0});
            visited[0][0] = true;
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                for (int j = 0; j < 4; j++) {
                    int nx = x + DIRECTIONS[j][0];
                    int ny = y + DIRECTIONS[j][1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                        queue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
            if (visited[m - 1][n - 1]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

并查集

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
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        int[] parent = new int[m * n];
        PriorityQueue<Edge> prior = new PriorityQueue<>((a, b) -> a.len - b.len);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int index = i * n + j;
                parent[index] = index;
                if (i < m - 1) {
                    prior.add(new Edge(index, index + n, Math.abs(heights[i][j] - heights[i + 1][j])));
                }
                if (j < n - 1) {
                    prior.add(new Edge(index, index + 1, Math.abs(heights[i][j] - heights[i][j + 1])));
                }
            }
        }
        int ans = 0;
        while (find(0, parent) != find(m * n - 1, parent)) {
            Edge edge = prior.poll();
            union(edge.x, edge.y, parent);
            ans = edge.len;
        }
        return ans;
    }

    private int find(int x, int[] parent) {
        if (x != parent[x]) {
            parent[x] = find(parent[x], parent);
        }
        return parent[x];
    }

    private void union(int a, int b, int[] parent) {
        int x = find(a, parent);
        int y = find(b, parent);
        parent[y] = x;
    }

    private class Edge {
        int x;
        int y;
        int len;

        Edge(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
    }
}

Dijkstra 算法

下面是题解的第三种方法 Dijkstra 算法的代码

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
class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] edge1, int[] edge2) {
                return edge1[2] - edge2[2];
            }
        });
        pq.offer(new int[]{0, 0, 0});

        int[] dist = new int[m * n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        boolean[] seen = new boolean[m * n];

        while (!pq.isEmpty()) {
            int[] edge = pq.poll();
            int x = edge[0], y = edge[1], d = edge[2];
            int id = x * n + y;
            if (seen[id]) {
                continue;
            }
            if (x == m - 1 && y == n - 1) {
                break;
            }
            seen[id] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && Math.max(d, Math.abs(heights[x][y] - heights[nx][ny])) < dist[nx * n + ny]) {
                    dist[nx * n + ny] = Math.max(d, Math.abs(heights[x][y] - heights[nx][ny]));
                    pq.offer(new int[]{nx, ny, dist[nx * n + ny]});
                }
            }
        }
        
        return dist[m * n - 1];
    }
}