1 条题解

  • 0
    @ 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%
上传者