首页 > 代码库 > poj3278(BFS)
poj3278(BFS)
题意:给出两个点代表人和牛的位置,人的运动方式有三种,牛原地不用,问人赶到牛的位置的最快速度;
key:刚开始找规律,其实规律都没规律,六组数据都过了那个碰巧。用bfs,搜到牛的位置结束,并返回步数(每个操作算一步)。注意牛可在人的左右边,要分开两种情况。
#include <iostream>#include <stdio.h>#include <string.h>#include <queue>const int maxn = 100000 + 5;int visit[maxn]; //标记是否访问int step[maxn]; //步数using namespace std;bool ok(int x) //判断是否超出数据范围{ if(x < 0 || x > 100001) return 1; else return 0;}int bfs(int a, int b){ int head, next; memset(visit, 0, sizeof(visit)); memset(step, 0, sizeof(step)); queue <int> que; //定义一个名为que的队列 que.push(a); //将第一个数放进队列里 visit[a] = 1; //标记这个点已经访问过 step[a] = 0; //起初步数为0 while(que.size()){ //判断队列是否为空,也可以表示为 !que.empty() head = que.front(); //将最前端的元素取出 que.pop(); for(int i = 0; i < 3; i++){ //有三种运动方式 if(i == 0) next = head - 1; if(i == 1) next = head + 1; if(i == 2) next = 2 * head; if(ok(next)) continue; //如果超出范围即结束本次循环 if(!visit[next]){ //如果这点没有访问过, que.push(next); //即把该点放进队列中, step[next] = step[head] + 1; //计算步数 visit[next] = 1; //标记已经访问 } if(next == b) //找到终点,就返回走到该点时的步数 return (step[next]); } }}int main(){ int n, m; scanf("%d%d", &n, &m); if(n >= m) //如果n > m只有一种运动方式 printf("%d\n", n - m); else //否则用广搜得到答案 printf("%d\n", bfs(n, m)); return 0;}
poj3278(BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。