1631.最小体力消耗路径

1631.最小体力消耗路径

题目

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

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

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

示例 1：

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

示例 2：

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

示例 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]<= 1000000

思路

首先我想到的是深度优先搜索/广度优先搜索，找到最小体力消耗路径。

但是，使用深度/广度优先搜索只能找到符合某个特定条件的路径，没有办法在搜索完毕后同时找到最小路径。

因此可以考虑将复杂问题转化为简单问题，即将原问题转化为两个相对简单的问题：

是否存在一条从左上角到右下角的路径，其经过的所有边权（节点间高度差）的最大值不超过 x？
这个x最小是几？

显然对问题1只需要对节点图进行一次深度/广度优先搜索即可解答，复杂度为O(mn)。

然后对问题2，我们可以在x的所有候选集的范围中去进行二分搜索，找到这个最小的x，复杂度为O(logC)，C是最大高度差999999。

总的复杂度是O(mnlogC)。

本题的核心思想是，将一个复杂问题转化为两个相对简单问题的集合。通过分别解决这两个相对简单的问题，最终解决困难问题。

代码

下面代码可以对二分查找和广度优先搜索的写法进行一个很好的复习。

class Solution {
    private int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 方向盘
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int columns = heights[0].length;

        int left = 0;
        int right = 999999;
        int result = 0;
        while (left <= right) { // 二分查找
            int mid = (left + right)/2;
            int[][] seen = new int[rows][columns];
            Queue<int[]> queue = new LinkedList<int[]>();

            int exist = 0;
            queue.offer(new int[]{0, 0});
            while (!queue.isEmpty()) { // 广度优先搜索
                int[] point = queue.poll();
                int x = point[0];
                int y = point[1];
                for (int[] dir : direction) {
                    int xnext = x + dir[0];
                    int ynext = y + dir[1];
                    if (xnext >= 0 && xnext < rows 
                    && ynext >= 0 && ynext < columns 
                    && seen[xnext][ynext] == 0
                    && Math.abs(heights[xnext][ynext] - heights[x][y]) <= mid) {
                        if (xnext == (rows - 1) && ynext == (columns - 1)){
                            exist = 1;
                            break;
                        }
                        queue.offer(new int[]{xnext, ynext});
                        seen[xnext][ynext] = 1;
                    }
                }
            }
            if (exist == 0) {
                left = mid + 1;
            } else {
                result = mid;
                right = mid - 1;
            }
        }
        return result;
    }
}