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; }
下一篇: WARNING OGG-01519