抓住那头牛
【摘要】
大致题意:
在一个坐标轴上,农夫在N点,牛在K点(假设在整个过程中牛静止不动),现在农夫可以 +1, -1, *2 的步数,问抓到牛的最小步数
采用STL的queue 第一次使用。。。
#...
大致题意:
在一个坐标轴上,农夫在N点,牛在K点(假设在整个过程中牛静止不动),现在农夫可以 +1, -1, *2 的步数,问抓到牛的最小步数
采用STL的queue 第一次使用。。。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int N, K;
const int MAXN=100000;
int visited[MAXN+10];
struct Step
{
int x;
int steps;
Step(int xx, int s):x(xx),steps(s){}
};
queue <Step> q;
int main()
{
cin >> N >> K;
memset(visited, 0, sizeof(visited));
q.push(Step(N, 0));
visited[N] = 1;
while( !q.empty())
{
Step s=q.front();
if( s.x == K)
{
cout << s.steps << endl;
return 0;
}
else
{
if( s.x-1>=0 && !visited[s.x-1])
{
q.push(Step(s.x-1, s.steps+1));
visited[s.x-1] = 1;
}
if( s.x+1<=MAXN && !visited[s.x+1])
{
q.push(Step(s.x+1, s.steps+1));
visited[s.x+1] = 1;
}
if( s.x*2<=MAXN && !visited[s.x*2])
{
q.push(Step(s.x*2, s.steps+1));
visited[s.x*2] = 1;
}
q.pop();
}
}
return 0;
}
文章来源: recclay.blog.csdn.net,作者:ReCclay,版权归原作者所有,如需转载,请联系作者。
原文链接:recclay.blog.csdn.net/article/details/64465753
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)