700字范文,内容丰富有趣,生活中的好帮手!
700字范文 > AcWing . 拖拉机(双端BFS)

AcWing . 拖拉机(双端BFS)

时间:2022-12-21 22:08:01

相关推荐

AcWing . 拖拉机(双端BFS)

题目链接

/problem/content//

思路

一个有0代价和1代价边权的最短路,我们用双端队列将0和1边权用一个双端队列分开存储,然后进行一个类迪杰斯特拉的最短路即可,值得注意的是,这个二维平面是无限大的,但是我们只需要多使用一层(这一圈都是空的)就好了,因为效果都一样,详情请看代码

代码

#include <bits/stdc++.h>using namespace std;const int N = 1e3+10;bool mp[N][N];int dis[N][N];bool vis[N][N];typedef pair<int,int> PII;int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};bool check(int x,int y) {if(x >= 0 && x < N && y >= 0 && y < N) {return true;}return false;}int bfs(int sx,int sy){deque<PII> que;que.push_back({sx,sy});memset(dis,0x3f,sizeof dis);dis[sx][sy] = 0;while(!que.empty()){PII p = que.front();que.pop_front();int x = p.first;int y = p.second;if(vis[x][y]) continue;vis[x][y] = true;if(x == 0 && y == 0) break;for(int i = 0;i < 4; ++i) {int nx = x + dy[i];int ny = y + dx[i];if(check(nx,ny)) {int w = 0;if(mp[nx][ny]) w = 1;if(dis[nx][ny] > dis[x][y] + w) {dis[nx][ny] = dis[x][y] + w;if(!w) que.push_front({nx,ny});else que.push_back({nx,ny});}}}}return dis[0][0];}int main(){int n,sx,sy;cin>>n>>sx>>sy;int x,y;for(int i = 1;i <= n; ++i) {cin>>x>>y;mp[x][y] = true;}cout<<bfs(sx,sy)<<endl;return 0;}

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。