html简单网站开发案例,企业网站建设报价单,动易企业网站,qq空间主页制作网站题目#xff1a;
农夫知道一头牛的位置#xff0c;想要抓住它。农夫和牛都于数轴上 #xff0c;农夫起始位于点 N(0N100000) #xff0c;牛位于点 K(0K100000) 。农夫有两种移动方式#xff1a; 1、从 X移动到 X-1或X1 #xff0c;每次移动花费一分钟 2…题目
农夫知道一头牛的位置想要抓住它。农夫和牛都于数轴上 农夫起始位于点 N(0N100000) 牛位于点 K(0K100000) 。农夫有两种移动方式 1、从 X移动到 X-1或X1 每次移动花费一分钟 2、从 X移动到 2*X 每次移动花费一分钟 假设牛没有意识到农夫的行动站在原地不。最少要花多少时间才能抓住牛 Input 一行: 以空格分隔的两个字母: N 和 K Output 一行: 农夫抓住牛需要的最少时间单位分钟 Sample Input 5 17 Sample Output 4 Hint 农夫使用最短时间抓住牛的方案如下: 5-10-9-18-17, 需要4分钟.
分析与解答
由于无法确定深度因此用bfs广搜bfs不需要回溯是一层一层推进一直到最后的解 这题有三种情况后退一步前进一步前进二倍当前距离那我们就层次遍历每层输入到队列里输完了就把上一层pop掉就是不断遍历并且查找遇到最终结果return并输出time即可 为了减小时间我们需要判重每次只入那些曾经没出现过的数。 这一类bfs具体怎么实现就是先建一个队列然后把第一个数push里面只要队列不空就一直对队列进行出队入队操作。需要有两个变量 m,next;m存的是根结点每次循环最初需要把他取出next存的是由根结点1-1*2从而形成的子结点我们存子结点时注意判重不重复我们就push next并且标记。注意每次操作完之后我们都要检查一下是不是满足最终的结果如果满足我们直接return就行
代码参考https://blog.csdn.net/qq_38620461/article/details/78445374
#includebits/stdc.h
using namespace std;
int to[2]{1,-1};
int a,b,sum;
int vis[100000];
struct place
{int x,time;
};
int check(place k)
{if(k.x0||k.x100000||vis[k.x]1)return 0;return 1;
}
int bfs(place n)
{place m,next;queueplacew;w.push(n);while(!w.empty()) {mw.front();w.pop();if(m.xb)return m.time;for(int i0;i2;i){next.xm.xto[i];next.timem.time1;if(next.xb)return next.time;if(check(next)){w.push(next);vis[next.x]1;}}next.xm.x*2;next.timem.time1;if(next.xb)return next.time;if(check(next)){w.push(next);vis[next.x]1;}}return 0;
}
int main()
{int i,j,t;place x1;while(~scanf(%d %d,a,b)){memset(vis,0,sizeof(vis));x1.xa;x1.time0;vis[x1.x]1;sum0;sumbfs(x1);printf(%d\n,sum);}return 0;
}
