🔥博客主页： A_SHOWY
🎥系列专栏：力扣刷题总结录 数据结构 云计算 数字图像处理
1631. 最小体力消耗路径
https://leetcode.cn/problems/path-with-minimum-effort/这道题目的核心思路是：使用了二分查找和BFS （深度优先遍历）结合的方式来解决路径搜索问题，在每一次二分查找中，通过 BFS 来检查是否存在满足条件的路径，并不断调整查找的范围，直到找到满足条件的最小值为止
第一步
static constexpr int dirs[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};static:关键字用于声明类的静态成员变量或函数,constexpr关键字用于声明常量表达式,连起来用于声明静态常量成员变量
dirs：用于表示四个方向的偏移量。这个数组是一个2维数组，包含了4个方向的偏移值。
{ -1, 0 } 表示向左移动一个单位（在二维平面上，x轴减少1，y轴不变）。
{ 1, 0 } 表示向右移动一个单位（在二维平面上，x轴增加1，y轴不变）。
{ 0, -1 } 表示向上移动一个单位（在二维平面上，y轴减少1，x轴不变）。
{ 0, 1 } 表示向下移动一个单位（在二维平面上，y轴增加1，x轴不变）。
第二步
queue<pair<int,int>> q;//定义一个队列存储BFS中待访问的结点坐标
q.emplace(0,0);
//创建一个数组，记录已经访问过的结点
vector<int> seen(m*n);
seen[0] = 1;1.声明了一个队列 q，这个队列用于在 BFS 中存储待访问的节点坐标。这里使用了 pair<int, int>，表示一个二维平面上的点的坐标，pair 类型中的两个整数分别表示 x 和 y 坐标。
2.将起始节点的坐标 (0, 0) 放入队列 q 中。在 BFS 中，通常从起始节点开始遍历或搜索。
3.创建了一个大小为 m * n 的 seen 数组，用于标记已经访问过的节点。这个数组在 BFS 中用于避免重复访问节点（存储方式是m*x + y）
4.将起始节点 (0, 0) 所代表的索引位置（假设是二维平面中的第一个节点）标记为已访问，即将 seen 数组中对应的位置值设为 1
int m = heights.size();//行数
int n = heights[0].size();//列数表示行数和列数
第三步
while(!q.empty()){
//BFS
auto[x,y] = q.front();
q.pop();
for(int i = 0;i < 4; i++){
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];//计算当前节点 (x, y) 的第 i 个方向上相邻节点的坐标
if(nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && abs(heights[x][y]-heights[nx][ny]) <= mid){
q.emplace(nx,ny);//如果相邻节点满足条件，将其坐标 (nx, ny) 加入队列 q，表示将要访问这个节点。
seen[nx * n + ny] = 1;//同时标记这个相邻节点为已访问（在 seen 数组中将其对应位置的值设为 1），避免重复访问
}
} 当队列 q 不为空时执行，意味着还有待访问的节点，从队列 q 中取出队首元素（当前节点的坐标），并将其分别赋值给变量 x 和 y。然后将该节点从队列中移出。计算当前节点 (x, y) 的第 i 个方向上相邻节点的坐标。如果相邻节点满足条件，将其坐标 (nx, ny) 加入队列 q，表示将要访问这个节点。同时标记这个相邻节点为已访问（在 seen 数组中将其对应位置的值设为 1），避免重复访问。
abs() 是 C++ 中的一个函数，用于计算数值的绝对值。
第四步
if(seen[m * n -1]){//最后一个进入到数组中了已经被访问
ans = mid;
right = mid -1;
}
else{
left = mid + 1;
}二分法部分当 if(seen[m * n -1])表示最后一个进入到数组中了已经被访问
所以总体代码实现为
class Solution {
private:
static constexpr int dirs[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int left = 0; int right = 999999;//十的六次方-1
int ans = 0;
while(left <= right){
int m = heights.size();//行数
int n = heights[0].size();//列数
int mid = left + ((right - left)/2);
queue<pair<int,int>> q;//定义一个队列存储BFS中待访问的结点坐标
q.emplace(0,0);
//创建一个数组，记录已经访问过的结点
vector<int> seen(m*n);
seen[0] = 1;
while(!q.empty()){
//BFS
auto[x,y] = q.front();
q.pop();
for(int i = 0;i < 4; i++){
int nx = x + dirs[i][0];
int ny = y + dirs[i][1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && !seen[nx * n + ny] && abs(heights[x][y]-heights[nx][ny]) <= mid){
q.emplace(nx,ny);
seen[nx * n + ny] = 1;
}
}
}
if(seen[m * n -1]){//最后一个进入到数组中了已经被访问
ans = mid;
right = mid -1;
}
else{
left = mid + 1;
}
}
return ans;
}
};有一个注意的点，注意看heights大小的最大值为10的六次方，所以我们right初始值为10的六次方-1.
