POJ3278 Catch That Cow(BFS)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了POJ3278 Catch That Cow(BFS)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1917字，纯文字阅读大概需要3分钟。
内容图文
题目链接：http://poj.org/problem?id=3278
题意：
在一个数轴上(0 ~ 100000),给你农夫J的位置N,和牛cow的位置K,农夫有三种移动的方式:左移一步(X - 1,X为当前位置);右移一步(X + 1);右移2*X步(2 * X);问农夫最少移动多少步可以追赶到牛,牛是原地不动的.
思路:
既然问的是最少移动多少步,最容易想到的就是暴力了,假设从起点开始每步有三个选择,选择一个点之后,接下来还是有三种选择.......这样就构造了一颗完全三叉树,即问题的解空间.由于问题问得是最短距离,即尽可能浅的访问到这棵树中的目标点.很明显的采用BFS就好了～
注意：
点的下界是 0,上界是 100000,所以BFS时判断点是否访问之前,应该先判断点是否在界限之内.单纯的吃了四五发RE......
代码：
1 #include <iostream>
2 #include <cmath>
3 #include <cstdio>
4 #include <cstring>
5 #include <cstdlib>
6 #include <stack>
7 #include <queue>
8 #include <vector>
9 #include <algorithm>
10 #include <string>
1112 typedef longlong LL;
13usingnamespace std;
14constint MAXN = 100000;
15int visit[MAXN + 3];//标记数组16int FJ, cow;
1718 typedef struct Point { int x; int step; } Poi;
1920int check(int k) {//判断点是否在界限之内21if(k >= 0 && k <= MAXN) return1;
22return0;
23}
2425int BFS(Poi st) {//从农夫的起始点开始搜索解答树26 queue<Poi> Qu;
27 Qu.push(st);
28 visit[st.x] = 1;
29int ans = -1;
30while(!Qu.empty()) {
31 Poi now;
32 now = Qu.front();
33 Qu.pop();
34 ans = now.step;
35if(now.x == cow) break;//到达目标点36if(check(now.x + 1) && !visit[now.x + 1]) {//先判断点的范围再判断是否访问, 三个 if 分别为三种移动方式37 Poi nex;
38 nex.x = now.x + 1, nex.step = now.step + 1;
39 Qu.push(nex);
40 visit[nex.x] = 1;
41 }
42if(check(now.x -1) && !visit[now.x - 1]) {
43 Poi nex;
44 nex.x = now.x - 1, nex.step = now.step + 1;
45 Qu.push(nex);
46 visit[nex.x] = 1;
47 }
48if(check(now.x * 2) && !visit[now.x * 2]) {
49 Poi nex;
50 nex.x = now.x * 2, nex.step = now.step + 1;
51 Qu.push(nex);
52 visit[nex.x] = 1;
53 }
54 }
55return ans;
56}
5758int main() {
59while(~scanf("%d%d", &FJ, &cow)) {
60 memset(visit, 0, sizeof(visit));
61 Poi st;
62 st.x = FJ, st.step = 0;
63 printf("%d\n", BFS(st));
64 }
65return0;
66 }
原文：http://www.cnblogs.com/Ash-ly/p/5732311.html
内容总结
以上是互联网集市为您收集整理的POJ3278 Catch That Cow(BFS)全部内容，希望文章能够帮你解决POJ3278 Catch That Cow(BFS)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。