Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

Input

Output

Sample Input

1

5 5 14

S*#*.

.#…

…..

****.

…#.

..*.P

#.*..

***..

…*.

*.#..

Sample Output

YES

Source

HDU 2007-6 Programming Contest

AC代码：

#include <cstdio>
#include <queue>
using namespace std;
int n, m, t;
char map[3][15][15];
const int dx[] = {0, 0, 1, -1},
dy[] = {1, -1, 0, 0};
struct node
{
int x, y, z, step;
bool operator == (const node b) const
{
return x == b.x && y == b.y && z == b.z;
}
};
node start, goal;
queue <node> q;
void input()
{
scanf("%d%d%d", &n, &m, &t);
for (int i = 0; i < n; i++)
scanf("%s", map[0][i]);
for (int i = 0; i < n; i++)
scanf("%s", map[1][i]);
}
bool check(int z, int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= m || map[z][x][y] == '*')
return 0;
return 1;
}
void pre()
{
while (!q.empty())
q.pop();
for (int i = 0; i < 2; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < m; k++)
{
if (map[i][j][k] == 'P')
goal = (node){j, k, i, 0};
if (map[i][j][k] == '#')
{
if (map[!i][j][k] == '*')
map[i][j][k] = '*';
else if (map[!i][j][k] == '#')
map[i][j][k] = map[!i][j][k] = '*';
}
}
start = (node){0, 0, 0, 0};
map[0][0][0] = '*';
}
void bfs()
{
pre();
q.push(start);
while (!q.empty())
{
node u = q.front();
q.pop();
if (u == goal && u.step <= t)
{
printf("YES\n");
return;
}
if (u.step > t)
break;
node next;
for (int i = 0; i < 4; i++)
{
next.x = u.x + dx[i];
next.y = u.y + dy[i];
if (!check(u.z, next.x, next.y))
continue;
if (map[u.z][next.x][next.y] == '#')
next.z = !u.z;
else
next.z = u.z;
next.step = u.step + 1;
map[next.z][next.x][next.y] = '*';
q.push(next);
}
}
printf("NO\n");
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
input();
bfs();
}
return 0;
}