欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

OpenJudge 4001:抓住那头牛

程序员文章站 2022-07-05 15:33:19
"题目链接" 题解: 这个题可以用广搜来解决,从农夫到牛的走法每次都有三种选择,定义一个队列,把农夫的节点加进队列,然后以这三种走法找牛,队列先进先出,按顺序直到找到牛的位置。 代码: c++ include include include include using namespace std; ......

题解:

这个题可以用广搜来解决,从农夫到牛的走法每次都有三种选择,定义一个队列,把农夫的节点加进队列,然后以这三种走法找牛,队列先进先出,按顺序直到找到牛的位置。

代码:

#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
int n,k;
#define max 1e5
const int max_n=1e5+5;
int vist[max_n];
struct step
{
    int x,sts;
    step(int xx,int s):x(xx),sts(s){}   //构造函数,但是有自定义构造函数以后,默认的构造函数不再起作用,所以如果有不赋初值的参数,需要再定义一个空构造函数 
    step(){}    //空构造函数 
};
queue<step> q;
int main()
{
    scanf("%d%d",&n,&k);
    memset(vist,0,sizeof(vist));
    q.push(step(n,0));   
    vist[n]=1;
    while(!q.empty()){
        step s=q.front();
        if(s.x==k){               //找到牛所在的位置 
            printf("%d\n",s.sts);
            break;
        }
        else{                           //三种情况 
            if(s.x-1>=0&&!vist[s.x-1]){        
                q.push(step(s.x-1,s.sts+1));
                vist[s.x-1]=1;
            }
            if(s.x+1<=max&&!vist[s.x+1]){
                q.push(step(s.x+1,s.sts+1));
                vist[s.x+1]=1;
            }
            if(s.x*2<=max&&!vist[s.x*2]){
                q.push(step(s.x*2,s.sts+1));
                vist[s.x*2]=1;
            }   
        }
        q.pop();                //把走过的点走从队列里删掉 
    }
    return 0;
}