AcWing 1100. 抓住那头牛
原题链接
简单
作者:
一抹斜阳
,
2019-12-11 22:10:59
,
所有人可见
,
阅读 1043
#include<iostream>
#include<queue>
using namespace std;
struct step
{
int x;
int d;
step(int a, int b) :x(a),d(b)
{
}
};
const int MAX = 100000;
int n, k;
int used[MAX + 10];
int bfs();
int main()
{
cin >> n >> k;
cout << bfs() << endl;
return 0;
}
int bfs()
{
queue<step> q;
q.push(step(n, 0));
used[n] = 1;
while (!q.empty())
{
step s = q.front();
if (s.x == k)
{
return s.d;
}
else
{
if (s.x + 1 <= MAX && used[s.x + 1] == 0)
{
q.push(step(s.x + 1, s.d + 1));
used[s.x + 1] = 1;
}
if (s.x - 1 >= 0 && used[s.x - 1] == 0)
{
q.push(step(s.x - 1, s.d + 1));
used[s.x - 1] = 1;
}
if (s.x * 2 <= MAX && used[s.x * 2] == 0)
{
q.push(step(s.x * 2, s.d + 1));
used[s.x * 2] = 1;
}
q.pop();
}
}
}