首页 > POJ解题报告 > POJ 3278 Catch That Cow[BFS]

POJ 3278 Catch That Cow[BFS]

复习数据结构ing,现在做做简单的题目。这是很久以前做的入门的题,翻出来了。用BFS做,如果只用一个队列,那么需要定义结构体来存储节点的位置信息和时间信息;如果不想用结构体的话需要两个队列,这样是一层一层的遍历节点,就只需要一个整型来记录时间信息了。其实都差不多,具体实现手法不同而已,BFS的思想是不变的。

下面两个版本的代码都贴一下,

POJ 3278 Catch That Cow[BFS] [http://poj.org/problem?id=3278]

#include <iostream>
#include <queue>
#define MAX 200010
using namespace std;
 
int BFS(int n, int k)
{
	queue<int> q;
	int res = 0, flag[MAX] = {0};
	int find = 0, t;
	q.push(n);
	flag[n] = 1;
	while(true)
	{
		queue<int> tmp;
		while(!q.empty())
		{
			t = q.front();
			q.pop();
			tmp.push(t);
		}
		while(!tmp.empty())
		{
			t = tmp.front();
			tmp.pop();
			if(t == k)
			{
				return res;
			}
			if(t + 1 < MAX && !flag[t+1])
			{
				q.push(t+1);
				flag[t+1] = 1;
			}
			if(t - 1 >= 0 && !flag[t-1])
			{
				q.push(t-1);
				flag[t-1] = 1;
			}
			if(2*t < MAX && !flag[2*t])
			{
				q.push(2*t);
				flag[2*t] = 1;
			}
		}
		++res;
	}
}
 
int main(int argc, char **argv)
{
	int n, k;
	while(EOF != scanf("%d %d", &n, &k))
	{
		printf("%d\n", BFS(n, k));
	}
	return
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
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
 
#define MAX_NUM 200010
 
typedef struct _S_NODE
{
	int pos;
	int time;
} Node;
 
int main(int argc, char **argv)
{
	int n, k;
	while (EOF != scanf ("%d %d", &n, &k))
	{
		queue<Node> q;
		bool flag[MAX_NUM] = {0};
		Node tmp;
		tmp.time = 0;
		tmp.pos = n;
		q.push(tmp);
		while (!q.empty())
		{
			tmp = q.front();
			q.pop();
			// ok ?
			if (tmp.pos == k)
			{
				printf("%d\n", tmp.time);
				break;
			}
			Node node = tmp;
			// pos-1
			++node.time;
			--node.pos;
			if (node.pos < MAX_NUM && node.pos >= 0 && !flag[node.pos])
			{
				q.push(node);
				flag[node.pos] = 1;
			}
			// pos+1
			node = tmp;
			++node.time;
			++node.pos;
			if (node.pos < MAX_NUM && !flag[node.pos])
			{
				q.push(node);
				flag[node.pos] = 1;
			}
			// pos*2
			node = tmp;
			++node.time;
			node.pos *= 2;
			if (node.pos < MAX_NUM && !flag[node.pos])
			{
				q.push(node);
				flag[node.pos] = 1;
			}
		}
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 3278 Catch That Cow[BFS]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.