AcWing 1100. 抓住那头牛
原题链接
简单
#include <iostream>
#include <queue>
using namespace std;
const int nm = 1e5 + 10;
int st[nm];
int n,k;
int dir[3] = {-1,1,1};//定义方向向前走 向后走 两倍的距离跳转
struct Node{
int x;//当前位置
int path;//所需要的最短步数
};
void bfs()
{
queue <Node> q;
Node now,next;//当前状态和下一个状态
now.x = n;//起点入队
now.path = 0;
q.push(now);
st[1] = 1;
while(q.size())
{
now = q.front();
if(now.x == k)
{
cout << now.path<<endl;
return;
}
dir[2] = now.x;
for(int i = 0;i<3;i++)
{
next.x = now.x + dir[i];//状态转移
if(next.x > nm||next.x <0 ||st[next.x]) continue;//超过目标的话直接退出
st[next.x] = 1;//标记已经用过
next.path = now.path + 1;
q.push(next);
}
q.pop();
}
}
int main()
{
cin >> n >>k;
bfs();
return 0;
}