网站怎么做pc端盒子,杭州网站建设杭州,游戏试玩网站怎么做,园林景观设计公司经营范围思路#xff1a;BFS二分
这道题和洛谷上的那个“汽车拉力赛”那道题很相似#xff0c;但是这道题相较于洛谷那个来说会简单一些。
这里作者一开始写的时候思路堵在了怎么在BFS中用二分#xff0c;先入为主的以为需要先写出来搜索函数然后再去处理二分的事#xff0c;但是…思路BFS二分
这道题和洛谷上的那个“汽车拉力赛”那道题很相似但是这道题相较于洛谷那个来说会简单一些。
这里作者一开始写的时候思路堵在了怎么在BFS中用二分先入为主的以为需要先写出来搜索函数然后再去处理二分的事但是这里是先二分找数然后再搜索才是对的。所以先入为主之后就没有做出来。
注意需要注意数据范围另外每一次更新mid数值的时候我们上一次已经搜索过的数组队列等存储单元都需要清空不然的话会影响后面的输出结果。还有二分注意用哪一个模板选择也是很重要的。这里主要是求最小值所以是(leftright)/2而不是(leftright1)/2还有就是while中不要leftright你用范围的二分查找会造成死循环但是用于基本的找数是可以的。
class Solution {
public:int minimumEffortPath(vectorvectorint heights) {int dx[4]{1,-1,0,0};int dy[4]{0,0,1,-1};int left0;int right1000000;while(leftright){queuepairint,intq;q.push({0,0});vectorvectorboolst(heights.size(),vectorbool(heights[0].size(),false));st[0][0]true;int mid(leftright)/2;while(!q.empty()){auto tmpq.front();q.pop();for(int i0;i4;i){int adx[i]tmp.first;int bdy[i]tmp.second;if(aheights.size()||a0||b0||bheights[0].size())continue;if(st[a][b])continue;if(abs(heights[a][b]-heights[tmp.first][tmp.second])mid)continue;q.push({a,b});st[a][b]true;}}if(st[heights.size()-1][heights[0].size()-1]){rightmid;}else{leftmid1;}}return right;}
};
