poj3278 Catch That Cow

Posted on | In |

题意

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上
，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)
。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要
花多少时间才能抓住牛？

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

思路

bfs搜索 记录访问过的节点 若已走过就不再访问 再访问下一层

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <queue>
const int	MAXN = 100000;
int		vis[MAXN + 10];
using namespace std;
struct point {
	int x, l;
	point( int xx, int ll ) : x( xx ), l( ll )
	{
	}
};
bool bfs( int m, int n )
{
	queue<point> q;
	q.push( point( m, 0 ) );
	vis[m] = 1;
	while ( !q.empty() )
	{
		point p = q.front();
		if ( p.x == n )
		{
			cout << p.l << endl;
			return(true);
		}
		q.pop();
		if ( p.x - 1 >= 0 && !vis[p.x - 1] )
		{
			q.push( point( p.x - 1, p.l + 1 ) );
			vis[p.x - 1] = 1;
		}
		if ( p.x + 1 <= MAXN && !vis[p.x + 1] )
		{
			q.push( point( p.x + 1, p.l + 1 ) ); vis[p.x + 1] = 1;
		}
		if ( p.x * 2 <= MAXN && p.x * 2 >= 0 && !vis[p.x * 2] )
		{
			q.push( point( p.x * 2, p.l + 1 ) ); vis[p.x * 2] = 1;
		}
	}
	return(false);
}


int main()
{
	int n, k;
	cin >> n >> k;
	memset( vis, 0, sizeof(vis) );
	bfs( n, k );
	return(0);
}