1 条题解

  • 0
    @ 2018-12-16 12:53:35

    这题你们可能不会

    这是题解

    使用构造函数

    //抓住那头牛(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);
        //ss.x=N;ss.steps=0;
        memset(visited, 0, sizeof(visited));//初始化数组visited[]为零 
        q.push(Step(N, 0));//q.push(ss);//效果一样的 
        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])  //如果没有扩展过 
                {
                    //ss.x=s.x-1;ss.steps=steps+1;
                    q.push(Step(s.x-1, s.steps + 1));  //扩展,步数++ 
                    //不用构造函数 用结构体直接赋值也可 q.push(ss);
                    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;   
    } 
    

    不使用构造函数

    //抓住那头牛(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所需步数 
    };
    queue<Step> q;  //队列 
    int visited[MAXN + 5] = {}; //判重标记 , visited[i]=ture 表示i已扩展过 
    int main(){
        int N,K;
        scanf("%d%d", &N, &K);
        Step s,ss;
        s.x=N;
        s.steps=0;
        memset(visited, 0, sizeof(visited));//初始化数组visited[]为零 
        q.push(s);//效果一样的 
        visited[N] = 1;
        while(!q.empty()){
            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])  //如果没有扩展过 
                {
                    ss.x=s.x-1;
                    ss.steps=s.steps+1;//扩展,步数++ 
                    q.push(ss);
                    visited[s.x - 1] = 1;
                }
                if(s.x + 1 <= MAXN && !visited[s.x + 1])
                {
                    ss.x=s.x+1;
                    ss.steps=s.steps+1;//扩展,步数++ 
                    q.push(ss);
                    visited[s.x + 1] = 1;
                }
                if(s.x * 2 <= MAXN && !visited[s.x *2])
                {
                    ss.x=s.x*2;ss.steps=s.steps+1;//扩展,步数++ 
                    q.push(ss);
                    visited[s.x * 2] = 1;
                }
                q.pop();
            }
        }
        return 0;   
    } 
    
  • 1

信息

难度
5
分类
搜索 | 搜索 | 枚举 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者