【双端队列bfs】

【双端队列bfs】

笔记而已
推荐好文
推荐视频
双端队列bfs是解决0-1bfs最常用的一种手段
0-1bfs就是边值只有0或1两种情况时用的bfs
一般是求起点到终点所用边值总值最小为多少
用例题更好说明
1.拖拉机

这里，在通过没有干草块的位置时所用边值为零
通过有干草块位置时边值为1
要求需要移除最少的数量
那么一定是能不移就不移最好，实在需要移再移
换句话说，就是优先走没有干草块的位置，当走完没有干草块的位置时再走有干草块的位置

此时可以用双端队列deque来实现
将没有干草块的压入队头，有干草块的压入队尾
每次只用队头元素，就能实现先走边值为0，再走边值为1

不同于朴素bfs
0-1bfs不需要判重数组，一个点可能多次经过
但是，只有在值更小时才需要更新

代码

#include<bits/stdc++.h>//#define int long longusingnamespacestd;boolg[1015][1015];intdx[]={1,-1,0,0};intdy[]={0,0,1,-1};intdis[1015][1015];structnode{intx,y;};deque<node>dq;intn,x,y;voidbfs(intx,inty){dq.push_front((node){x,y});while(dq.size()){intax=dq.front().x,ay=dq.front().y;dq.pop_front();for(inti=0;i<4;i++){intsx=ax+dx[i],sy=ay+dy[i];if(sx>=0&&sx<=1010&&sy>=0&&sy<=1010){if(dis[sx][sy]<=dis[ax][ay]+g[sx][sy])continue;//只有值更小时，才需要更新if(!g[sx][sy])dq.push_front((node){sx,sy}),dis[sx][sy]=dis[ax][ay];if(g[sx][sy])dq.push_back((node){sx,sy}),dis[sx][sy]=dis[ax][ay]+1;if(!sx&&!sy)return;}}}}voidsolve(){cin>>n>>x>>y;while(n--){inta,b;cin>>a>>b;g[a][b]=1;}memset(dis,1e6,sizeof(dis));dis[x][y]=0;bfs(x,y);cout<<dis[0][0]<<endl;}signedmain(){intt=1;//cin>>t;while(t--){solve();}return0;}