1631.最小体力消耗路径

题目地址：https://leetcode.cn/problems/path-with-minimum-effort

答案:

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function(heights) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    const m = heights.length, n = heights[0].length;
    let left = 0, right = 999999, ans = 0;
    while(left <= right) {
        const mid = Math.floor((left + right) / 2)
        const queue = [[0, 0]]
        const seen = new Array(m * n).fill(0)
        seen[0] = 1
        while(queue.length) {
            const [x, y] = queue.shift()
            for(let i = 0; i < 4; i ++) {
                const nx = x + dirs[i][0]
                const ny = y + dirs[i][1]
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mid) {
                    queue.push([nx, ny])
                    seen[nx * n + ny] = 1
                }
            }
        }
        if(seen[m * n - 1]) {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return ans
};

首先确定方向

const dirs = [[-1, 0],  [1, 0], [0, -1], [0, 1]]

然后定义结果集的长宽

const m = heights.length, n = heights[0].length

定义循环的左边界和有边界和结果

let left = 0, right = 999999, ans = 0;

定义循环体

while(left <= right){}

确定中间点

const mid = Math.floor((left + right) / 2)

声明 点集合quene,并初始化为左上角第一个点

const quene = [[0,0]]

声明 结果集合seen，并初始化第一项为1

const seen = new Array(m * n).fill(0)
seen[0] = 1

开始循环点集合，然后上下左右方向不断移动，如果满足条件 在边界内、seen不存在、与移动前的点的绝对值小于mid，就加入点集合queue和结果集合seen

当循环queue完成后，判断是否到达边界，如果到达，mid中值赋值给ans，右边界左移；否则左边界右移。

最后返回ans。