02月
26

HDU-2102 A计划

发表于 • 本文总阅读数 次
字数统计: 448

简单搜索题

题目

  http://acm.hdu.edu.cn/showproblem.php?pid=2102

题意

  中文题，就不解释了哈。

解题思路

  从起点开始搜索四个方向就好了，用深度优先搜索和广度优先搜索都行，遇到#就搜索另一层。需要注意的是传送到另一层后，不只是要判断是不是墙，还要判断是不是#，因为按题意来说，这种情况会一直在两层之间传送，然后走不出去，如果不特判的话，会在另一层继续搜索。

代码

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
#include <stdio.h>
#include <string.h>

const int MAX_N = 12;

typedef struct node
{
	int x, y, z;
	int t;
} node;

int n, m, t;
char map[2][MAX_N][MAX_N];

int solve()
{
	int i, j, front, back;
	int book[2][MAX_N][MAX_N];
	node que[2 * MAX_N * MAX_N];
	node tep;
	int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	que[0] = (node){0, 0, 0, 0};
	front = 0;
	back = 1;
	memset(book, 0, sizeof(book));
	book[0][0][0] = 1;
	while(front != back)
	{
		for(i = 0; i < 4; i++)
		{
			tep = que[front];
			tep.x += dir[i][0];
			tep.y += dir[i][1];
			tep.t++;
			if(tep.x < 0 || tep.x >= n || tep.y < 0 || tep.y >= m || tep.t > t)
			{
				continue;
			}
			if(map[tep.z][tep.x][tep.y] == '#')
			{
				tep.z = !tep.z;
			}
			if(map[tep.z][tep.x][tep.y] == '*' || map[tep.z][tep.x][tep.y] == '#' || book[tep.z][tep.x][tep.y] == 1)
			{
				continue;
			}
			if(map[tep.z][tep.x][tep.y] == 'P')
			{
				return tep.t;
			}
			book[tep.z][tep.x][tep.y] = 1;
			que[back] = tep;
			back++;
		}
		front++;
	}
	return 0;
}

int main()
{
	int c, i, ans;

	scanf("%d", &c);
	while(c--)
	{
		scanf("%d %d %d", &n, &m, &t);
		getchar();
		for(i = 0; i < n; i++)
		{
			scanf("%s", map[0][i]);
		}
		getchar();
		for(i = 0; i < n; i++)
		{
			scanf("%s", map[1][i]);
		}

		ans = solve();
		if(ans == 0)
		{
			printf("NO\n");
		}
		else
		{
			printf("YES\n");
		}
	}
	return 0;
}
分享到：
0%