七台河网站seo,临沂企业网站,wordpress 微信客户端,记事本网站开发2023-12-11每日一题
一、题目编号
1631. 最小体力消耗路径二、题目链接
点击跳转到题目位置
三、题目描述
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights #xff0c;其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格…2023-12-11每日一题
一、题目编号
1631. 最小体力消耗路径二、题目链接
点击跳转到题目位置
三、题目描述
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights 其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) 且你希望去最右下角的格子 (rows-1, columns-1) 注意下标从 0 开始编号。你每次可以往 上下左右 四个方向之一移动你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。 示例 1
示例 2
示例 3 提示
rows heights.lengthcolumns heights[i].length1 rows, columns 1001 heights[i][j] 106
四、解题代码
int dir[4][2] {{-1, 0},{1, 0},{0, -1},{0, 1}
};
const int maxn 101;bool bfs(int height, vectorvectorint heights, int m, int n){int hash[maxn * maxn 100 6];memset(hash, 0, sizeof(hash));queueint path;path.push(0 * 100 0);hash[0 * 100 0] 1;while(!path.empty()){int tmp path.front();path.pop();int x tmp / maxn;int y tmp % maxn;if(x m - 1 y n - 1){return true;}for(int i 0; i 4; i){int tx x dir[i][0];int ty y dir[i][1];if(tx m || ty n || tx 0 || ty 0){continue;}if(hash[tx * maxn ty] 0 abs(heights[tx][ty] - heights[x][y]) height){hash[tx * maxn ty]1;path.push(tx * maxn ty);}}}
return false;
}class Solution {
public:int minimumEffortPath(vectorvectorint heights) {int left 0, right 999999;int ans 0;int m heights.size();int n heights[0].size();while(left right){int mid (leftright) 1;if(bfs(mid, heights, m, n) true){ans mid;right mid-1;}else{left mid 1;}}return left;}
};五、解题思路
(1) 利用图的四方向遍历。
(2) 二分答案来求解。
(3) 广度优先搜索来判断答案可不可行。
