首页 > POJ解题报告 > POJ 2251 Dungeon Master[三维BFS]

POJ 2251 Dungeon Master[三维BFS]

题目大意:给定一个三维的迷宫,看看能不能从起点走到终点,如果能的话就求出最短的时间(每次移动耗费一个时间单位)。
解题思路:还是搜索,只不过多加了一层;普通的搜索通常是二维情况下的,也就是在一个平面内进行搜索;而这个题目中的搜索范围是一个三维空间;考虑到求最短时间,所以可以用BFS作为搜索方法;二维也好三维也好,BFS的本质是不变的,只是增加了一个向上和向下的移动方向而已。

传送:POJ 2251 Dungeon Master http://poj.org/problem?id=2251

解题代码:

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;
 
#define MAX_NUM 31
 
class Node
{
public:
	int l, r, c;
	int time;
public:
	bool operator==(const Node& rhs) const
	{
		return l == rhs.l && r == rhs.r && c == rhs.c;
	}
};
 
int layer, row, col;
Node start, end;
bool dic[MAX_NUM][MAX_NUM][MAX_NUM];
bool flag[MAX_NUM][MAX_NUM][MAX_NUM];
int steps[6][3] = {{0, 0, 1}, {0, 0, -1}, 
{0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}};
 
bool CheckValid(const Node& node)
{
	int l = node.l, r = node.r, c = node.c;
 
	if (l >= 0 && l < layer 
		&& r >= 0 && r < row
		&& c >= 0 && c < col
		&& dic[l][r][c])
	{
		return true;
	}
	return false;
}
 
int TBFS()
{
	int i;
	queue<Node> q;
	q.push(start);
	flag[start.l][start.r][start.c] = 1;
 
	while (!q.empty())
	{
		Node tmp = q.front();
		q.pop();
 
		for (i = 0; i < 6; ++i)
		{
			Node node = tmp;
			node.l += steps[i][0];
			node.r += steps[i][1];
			node.c += steps[i][2];
			if (CheckValid(node) && !flag[node.l][node.r][node.c])
			{
				++node.time;
				flag[node.l][node.r][node.c] = 1;
				q.push(node);
 
				if (node == end)
				{
					return node.time;
				}
			}
		}
	}
	return 0;
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int i, j, k;
	char ch;
 
	while (1)
	{
		Node tmp;
		scanf ("%d %d %d%*c", &layer, &row, &col);
		if (!layer && !row && !col)
			break;
		for (i = 0; i < layer; ++i)
		{
			for (j = 0; j < row; ++j)
			{
				for (k = 0; k < col; ++k)
				{
					ch = getchar();
					if (ch == '#')
					{
						dic[i][j][k] = 0;
					}
					else if (ch == '.')
					{
						dic[i][j][k] = 1;
					}
					else if (ch == 'S')
					{
						start.l = i;
						start.r = j;
						start.c = k;
						start.time = 0;
						dic[i][j][k] = 1;
					}
					else if (ch == 'E')
					{
						end.l = i;
						end.r = j;
						end.c = k;
						end.time = 0;
						dic[i][j][k] = 1;
					}
				}
				getchar ();
			}
			getchar ();
		}
		memset(flag, 0, sizeof(flag));
		int ret = TBFS();
		if (ret)
		{
			printf ("Escaped in %d minute(s).\n", ret);
		}
		else
		{
			printf ("Trapped!\n");
		}
	}
	return 0;
}

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


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


更多



分类: POJ解题报告 标签: , ,
  1. 2011年9月10日21:38 | #1

    老兄,你的算法题还不少啊,呵呵,厉害!我现在是没有心思去看这些问题了,唉~~

    [回复]

    代码疯子 回复:

    @代码部落(Winson), 呵呵,都是些很简单的东西。一般工作的话可能算法用的少吧,我工作的时候也没多少时间来看这个,现在复习下 [em012]

    [回复]

  2. 2011年9月11日14:08 | #2

    看这种题目,我表示压力颇大

    [回复]

    代码疯子 回复:

    @C瓜哥, 稍微看看就懂了 [em012]

    [回复]

    C瓜哥 回复:

    @代码疯子, 我的意思不是说,看不懂,而是做这种题目,压力大
    我表示MFC害人不浅

    [回复]

    代码疯子 回复:

    @C瓜哥, 你是说MFC封装的太多了吗?还是认为做应用比较有趣就把时间放到应用开发上去了?
    我也发现MFC不适合初学者,一定要把Win32 SDK学好了再看MFC。
    我现在小玩意都用SDK写

    [回复]

    C瓜哥 回复:

    @代码疯子, 嗯,忽略掉了基础的学习

    [回复]