LeetCode 1631. 最小体力消耗路径：广度优先搜索BFS

本文主要是介绍LeetCode 1631. 最小体力消耗路径：广度优先搜索BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【LetMeFly】1631.最小体力消耗路径：广度优先搜索BFS

力扣题目链接：https://leetcode.cn/problems/path-with-minimum-effort/

你准备参加一场远足活动。给你一个二维 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] <= 10⁶

方法一：广度优先搜索BFS

首先我们可以构造一个图，图中顶点是矩阵中的点，图中的边是矩阵中相邻点的绝对值之差。

这样，我们只需要从起点0开始，使用一个优先队列进行广度优先搜索。每次找出未遍历的点中与已遍历的点中绝对值之差最小的点。入队时将“点的位置”和“从起点到该点的最大绝对值之差”入队。

最终返回最后一个位置距离起点的最大绝对值之差即为答案。

时间复杂度 $O(nm\log nm)$ ，其中 $size(graph)=n\times m$
空间复杂度 $O (nm)$

AC代码

C++

const int directions[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights) {int n = heights.size(), m = heights[0].size();vector<vector<pair<int, int>>> graph(n * m);  // graph[i]: [[j, 5], [k, 3]]for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int d = 0; d < 4; d++) {int ti = i + directions[d][0], tj = j + directions[d][1];if (ti < 0 || ti >= n || tj < 0 || tj >= m) {continue;}int diff = abs(heights[i][j] - heights[ti][tj]);int x = i * m + j, y = ti * m + tj;graph[x].push_back({y, diff});}}}auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;};priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);pq.push({0, 0});vector<int> ans(n * m, 1e9);  // 从0到i的最大绝对值之差ans[0] = 0;while (pq.size()) {auto [index, diff] = pq.top();pq.pop();for (auto [toIndex, toDiff] : graph[index]) {int nextDiff = max(diff, toDiff);if (ans[toIndex] > nextDiff) {ans[toIndex] = nextDiff;pq.push({toIndex, nextDiff});}}}return ans.back();}
};

Python

# from typing import List
# import heapqdirections = [[-1, 0], [1, 0], [0, -1], [0, 1]]class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:n, m = len(heights), len(heights[0])graph = [[] for _ in range(n * m)]for i in range(n):for j in range(m):for di, dj in directions:ti, tj = i + di, j + djif ti < 0 or ti >= n or tj < 0 or tj >= m:continuegraph[i * m + j].append((ti * m + tj, abs(heights[ti][tj] - heights[i][j])))pq = [(0, 0)]ans = [1000000000] * (n * m)ans[0] = 0while pq:thisDiff, thisNode = heapq.heappop(pq)for toNode, toDiff in graph[thisNode]:newDiff = max(thisDiff, toDiff)if ans[toNode] > newDiff:ans[toNode] = newDiffheapq.heappush(pq, (newDiff, toNode))# print(thisNode, toNode, newDiff)return ans[-1]