1631. 最小体力消耗路径

1631. 最小体力消耗路径

链接:https://leetcode-cn.com/problems/path-with-minimum-effort/

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

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

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

 

示例 1:

1631. 最小体力消耗路径

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

示例 2:

1631. 最小体力消耗路径

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

示例 3:

1631. 最小体力消耗路径

输入: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

思路1:最朴素的做法当然就是遍历出每一条路径,找出最终路径。我们尝试做一个剪枝,如果说我们设定一个阈值上限,当查找路径时发现当前边权值大于上限,就可以直接剪去当前的遍历;当整个图中存在一条满足阈值要求的边时,就可以认为该阈值可以满足,我们的任务就变成了找到一条满足这个阈值的最小值。因为1 <= heights[i][j] <= 10^6,所以题目所求的阈值上限不会超过10^6,这就是直接搜索答案的算法。我们可以加一个二分优化,设阈值A>B,若存在一条路径,使得路径上所有的边的权值都满足<=A,自然也就可以满足<=B。路径的搜索可以用DFS或BFS,当然BFS的遍历次数更少,更推荐BFS。不知道会不会有读者有疑惑,因为BFS是一种层次扩展的方式,可能在失败的路径上存在我们需要使用的边,直接在BFS过程中剪枝会不会丢掉可能满足要求的边呢,我们看一个图便知:

1631. 最小体力消耗路径

在上图中,A-B为红边,表示超过的阈值不满足要求,但是从A->B可以走满足要求的A-C-D-B,也就是说,从B出发到终点(因为能到达B,说明前面的路径都满足要求了)的路径可以被考虑,自然也就不会漏掉任何一个可能路径了。

class Solution {
public:

    bool visited[110][110];
    typedef pair<int,int> Node;

    bool BFS(vector<vector<int>>& heights,int n,int m,int M){
        memset(visited,0,sizeof(visited));
        queue<pair<int,int>> Que;
        Node node = Node{0,0};
        visited[0][0] = true;
        int i, j;
        Que.push(node);
        while(!Que.empty()){
            node = Que.front();
            Que.pop();
            i = node.first, j = node.second;

            if(i == n - 1 && j == m - 1) return true;

            if(i > 0 && !visited[i - 1][j] && abs(heights[i - 1][j] - heights[i][j]) <= M ){
                visited[i - 1][j] = true;
                Que.push(Node{i - 1,j});
            }
            if(i + 1 < n && !visited[i + 1][j] && abs(heights[i + 1][j] - heights[i][j]) <= M ){
                visited[i + 1][j] = true;
                Que.push(Node{i + 1,j});
            }
            if(j > 0 && !visited[i][j - 1] && abs(heights[i][j - 1] - heights[i][j]) <= M ){
                visited[i][j - 1] = true;
                Que.push(Node{i,j - 1});
            }
            if(j + 1 < m && !visited[i][j + 1] && abs(heights[i][j + 1] - heights[i][j]) <= M ){
                visited[i][j + 1] = true;
                Que.push(Node{i,j + 1});
            }
        }
        return false;
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(), m = heights[0].size(), i, j, L = 0, R = 1000000, M, ans = -1;
        while(L <= R){
            M = (L + R) >> 1;
            if(BFS(heights, n, m, M)){
                ans = M;
                R = M - 1;
            }else{
                L = M + 1;
            }
        }
        return ans;
    }
};

思路2:贪心思路构图。题意要求路径上的权值尽可能地小,我们就尽可能地多用小边;将所有的边权按照大小排序,并依次加入并查集中,当边权为value的边加入并查集后,发现左上角与右下角连通,则value为答案(因为我们加入的边权是单调非减的)。构建边集合的时候,我们只需要从左上遍历到右下,考虑右和下的边即可,而不需要对每个点都考虑上下左右(防止重复运算)。

class Solution {
public:

    int Father[10010], Index[110][110];

    struct Edge{
        int u, v, w;
        bool operator < (const Edge edge) const {
            return w < edge.w;
        }
    };

    Edge edge[20010];

    int LocateToIndex(int x,int y,int n,int m){
        return x * m + y;
    }

    int Find(int x){
        if(x == Father[x]) return x;
        return Father[x] = Find(Father[x]);
    }

    void Union(int A,int B){
        A = Find(A);
        B = Find(B);
        if(A != B){
            Father[A] = B;
        }
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        memset(Father,0,sizeof(Father));
        int n = heights.size(), m = heights[0].size(), i, j, cnt = 0, s, o;
        for(i = 0; i < n; ++ i){
            for(j = 0; j < m; ++ j){
                Index[i][j] = LocateToIndex(i, j, n, m);
                Father[Index[i][j]] = Index[i][j];
            }
        }
        for(i = 0; i < n; ++ i){
            for(j = 0; j < m; ++ j){
                if(i + 1 < n) edge[cnt ++] = Edge{Index[i][j], Index[i + 1][j], abs(heights[i][j] - heights[i + 1][j])};
                if(j + 1 < m) edge[cnt ++] = Edge{Index[i][j], Index[i][j + 1], abs(heights[i][j] - heights[i][j + 1])};
            }
        }
        sort(edge, edge + cnt);
        s = 0, o = n * m - 1;
        for(i = 0; i < cnt; ++ i){
            Union(edge[i].u, edge[i].v);
            if(Find(s) == Find(o)) return edge[i].w;
        }
        return 0;
    }
};

思路3:其实本题是对最短路的定义进行的更改,最短路的长度定义为路径上的边的最大长度。那如果我们使用最短路算法呢?单源最短路的经典算法Dijkstra,维护一个从源点S到当前点v的最短路径长度数组dist[v],每次基于已有的最短路径对其他路径进行更新。Dijkstra基于这样一种想法,每次dist数组内部最小的值对应的点v(不考虑已经成为过中继点的点),从S到它的最短距离是确定为dist[v]。

i 1 2 3 4 5 6
dist[i] 1 5 2 6 3 4
visited[i] yes no yes no yes no

在如上表格中,可以确定源点到1、3、5,当前要称为中继点的点是5,2、4、6已经分别使用经过1、3考虑,现在需要考虑的是是否能够通过5使得他们的路径长度变小。

这一想法的成立基础是更新逻辑保持单点不减,也就是说,考虑更多的点,答案不会变小。而对于max操作,也是一样的,考虑更多的点,答案也不会变小,因此Dijkstra可以解决这个问题。我们使用带单调队列优化的Dijkstra:

class Solution {
public:

    struct Dist{
        int i, j, w; // (i,j):到达点 w:dist[v]
        bool operator < (const Dist dist) const{
            return w > dist.w;
        }
    };

    bool visited[110][110]; // 已经确定dist[v]的点

    int minimumEffortPath(vector<vector<int>>& heights) {
        memset(visited,0,sizeof(visited));
        int n = heights.size(), m = heights[0].size(), i, j, cnt = 0, w, v, o = n * m - 1, index;
        priority_queue<Dist> pri_que;
        Dist dist;
        pri_que.push(Dist{0, 0, 0});
        while(!pri_que.empty()){
            dist = pri_que.top();
            pri_que.pop();
            i = dist.i, j = dist.j, w = dist.w;
            visited[i][j] = true;

            if(i == n - 1 && j == m - 1) return w;

            if(i > 0 && !visited[i - 1][j]){
                pri_que.push(Dist{i - 1, j, max(w, abs(heights[i][j] - heights[i - 1][j]) )});
            }

            if(i + 1 < n && !visited[i + 1][j]){
                pri_que.push(Dist{i + 1, j, max(w, abs(heights[i][j] - heights[i + 1][j]) )});
            }

            if(j > 0 && !visited[i][j - 1]){
                pri_que.push(Dist{i, j - 1, max(w, abs(heights[i][j] - heights[i][j - 1]) )});
            }

            if(j + 1 < m && !visited[i][j + 1]){
                pri_que.push(Dist{i, j + 1, max(w, abs(heights[i][j] - heights[i][j + 1]) )});
            }

        }
        return 0;
    }
};

 

 

 

上一篇:AI:2020年6月21日北京智源大会演讲分享之09:40Judea教授《 The New Science of Cause and Effect with reflections ondata s》


下一篇:地下迷宫探索