首页 > 代码库 > POJ3279 Catch That Cow(BFS)
POJ3279 Catch That Cow(BFS)
本文出自:http://blog.csdn.net/svitter
题意:给你一个数字n, 一个数字k,分别代表主人的位置和奶牛的位置,主任可以移动的方案有x+1, x-1, 2*x,求主人找到奶牛的时间(奶牛不移动)
题解:最基础的BFS但是脑子犯抽WA了3遍- =
注意:
1.数组范围1~1<<5
2.visit去重。(BFS最基础的)
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <queue> using namespace std; bool visit[100010]; struct step { int x; int t; step(){} step(int a, int b):x(a), t(b){} }; inline bool judgeNum(int i) { if(i > 100000 || i < 0) return false; return true; } int main() { int n, k; queue <step> que; step top; int temp; while(~scanf("%d%d", &n, &k)) { memset(visit, 0, sizeof(visit)); visit[n] = 1; que.push(step(n, 0)); while(!que.empty()) { top = que.front(); if(k == top.x) { printf("%d\n", top.t); while(!que.empty()) { que.pop(); } break; } temp = top.x+1; if(judgeNum(temp) && !visit[temp]) { que.push(step(top.x+1, top.t+1)); visit[temp] = 1; } temp = top.x-1; if(judgeNum(temp) && !visit[temp]) { que.push(step(top.x-1, top.t+1)); visit[temp]= 1; } temp = top.x*2; if(judgeNum(temp) && !visit[temp]) { que.push(step(2*top.x, top.t+1)); visit[temp] = 1; } que.pop(); } } return 0; }
POJ3279 Catch That Cow(BFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。