题意:中文题面
分析:双层BFS,之前写过类似的题.总结坑点:
1.步数小于等于T都是YES 2. 传送门的另一侧还是传送门或者墙都会死 3. 走到传送门也需要一步
#include <bits/stdc++.h>
using namespace std; char maze[2][11][11];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n, m, tot;
bool vis[2][11][11];
struct Point {
int x, y, z, step;
Point () {}
Point (int x, int y, int z, int step) : x (x), y (y), z (z), step (step) {}
};
Point s, e; bool check(int x, int y, int z) {
if (x < 1 || x > n || y < 1 || y > m || vis[z][x][y] || maze[z][x][y] == '*') return false;
else return true;
} bool BFS(void) {
memset (vis, false, sizeof (vis));
int res = 0x3f3f3f3f;
queue<Point> que; que.push (s);
vis[s.z][s.x][s.y] = true;
while (!que.empty ()) {
Point u = que.front (); que.pop ();
if (u.x == e.x && u.y == e.y && u.z == e.z) {
res = min (res, u.step); continue;
}
for (int i=0; i<4; ++i) {
int tx = u.x + dx[i], ty = u.y + dy[i], tz = u.z;
if (!check (tx, ty, tz)) continue;
if (maze[tz][tx][ty] == '#') {
if (maze[1-tz][tx][ty] == '*' || maze[1-tz][tx][ty] == '#' || vis[1-tz][tx][ty]) continue;
vis[1-tz][tx][ty] = true;
que.push (Point (tx, ty, 1 - tz, u.step + 1));
continue;
}
vis[tz][tx][ty] = true;
que.push (Point (tx, ty, tz, u.step + 1));
}
}
return res <= tot;
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d%d", &n, &m, &tot);
for (int k=0; k<2; ++k) {
if (k == 1) getchar ();
for (int i=1; i<=n; ++i) {
scanf ("%s", maze[k][i] + 1);
for (int j=1; j<=m; ++j) {
if (maze[k][i][j] == 'S') {
s = Point (i, j, k, 0);
}
else if (maze[k][i][j] == 'P') {
e = Point (i, j, k, 0);
}
}
}
}
if (BFS ()) puts ("YES");
else puts ("NO");
} return 0;
}