AcWing 1100. 很好理解的bfs
原题链接
简单
作者:
新.一
,
2021-04-26 17:31:56
,
所有人可见
,
阅读 380
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n,m;
queue<int>q;
int d[N];
int bfs(int x)
{
memset(d,-1,sizeof d);
int dx[3]={-1,1,1};
q.push(x);
d[x]=0;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=0;i<3;i++)
{
int a;
if(i==2) a=t+t;
else a=t+dx[i];
if(a<0||a>1e5) continue;
if(d[a]!=-1) continue;
if(a==m) return d[t]+1;
q.push(a),d[a]=d[t]+1;
}
}
return -1;
}
int main()
{
cin>>n>>m;
cout<<bfs(n);
return 0;
}
大佬的这个题解很简洁清晰~~