1 条题解
-
0不凉少年 LV 5 @ 2018-03-25 20:52:51
//抓住那头牛(POJ3278)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
using namespace std;
const int MAXN = 100000;
struct Step
{
int x; //位置
int steps; //表示到达x所需步数
Step(int xx, int s):x(xx), steps(s){} //定义后:xx 即 Step 中 x, s 即 Step 中 steps
};
queue<Step> q; //队列
int visited[MAXN + 5] = {}; //判重标记 , visited[i]=ture 表示i已扩展过
int main()
{
int N,K;
scanf("%d%d", &N, &K);
memset(visited, 0, sizeof(visited));
q.push(Step(N, 0));
visited[N] = 1;
while(!q.empty())
{
Step s = q.front(); //定义后:s 即 Step 结构体
if(s.x == K) //找到目标
{
printf("%d\n", s.steps);
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;
}
//加油哦
- 1
信息
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 60
- 已通过
- 17
- 通过率
- 28%
- 上传者