首页 > 代码库 > [poj] Catch That Cow--bfs
[poj] Catch That Cow--bfs
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Output
Sample Input
5 17
Sample Output
4
Hint
三个搜索方向 +1, -1, *2 用bfs搜索 数组要开到最大值的2倍 注意剪枝和边界问题
#include <iostream> #include <stdio.h> #include <queue> #include <cstring> using namespace std; const int Max = 210000; int s, e; struct node { int x, step; }now, Next; bool v[210000]; queue<node>q; int bfs() { now.x = s; now.step = 0; v[s] = 1; q.push(now); while (!q.empty()) { now = q.front(); q.pop(); if (now.x == e) return now.step; Next.x = now.x*2; Next.step = now.step+1; if (Next.x >= 0 && Next.x <= Max && !v[Next.x]){ q.push(Next); v[Next.x] = 1; } Next.x = now.x-1; Next.step = now.step+1; if (Next.x >= 0 && Next.x <= Max && !v[Next.x]){ q.push(Next); //若先检查v[Next.x] 会出现数组越界v[-1]的情况 v[Next.x] = 1; } Next.x = now.x+1; Next.step = now.step+1; if (Next.x >= 0 && Next.x <= Max && !v[Next.x]){ q.push(Next); v[Next.x] = 1; } } return 0; } int main() { //freopen("1.txt", "r", stdin); cin >> s >> e; memset(v, 0, sizeof(v)); cout << bfs(); return 0; }
[poj] Catch That Cow--bfs