1631. 最小体力消耗路径

原题链接

题目描述

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

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

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

---

分析

二分最少消耗的体力值+bfs

具体见代码

代码

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    bool bfs(vector<vector<int>>& heights, int mid) {
        int n = heights.size(), m = heights[0].size();
        queue<pair<int, int>> q;
        vector<vector<bool>> st(100, vector<bool> (100));
        q.push({0, 0});
        st[0][0] = true;

        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();

            if (x == n - 1 && y == m - 1) return true;

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny] ||
                    abs(heights[x][y] - heights[nx][ny]) > mid) continue;
                q.push({nx, ny});
                st[nx][ny] = true;
            }
        }
        return false;
    }

    int minimumEffortPath(vector<vector<int>>& heights) {
        int n = heights.size(), m = heights[0].size();
        if (n == 1 && m == 1) return 0;

        int l = 0, r = int(1e6);
        while (l < r) {
            int mid = l + r >> 1;
            if (bfs(heights, mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};