$$\color{Purple}{kuangbin题解目录}$$
描述
可怜的公主在一次次被魔王掳走,一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。
魔王已经发出消息说将在 $T$ 时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。
年迈的国王正是心急如焚,告招天下勇士来拯救公主。
不过公主早已习以为常,她深信智勇的骑士 LJ 肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口 $(0,0,0)$ 用 S
表示,公主的位置用 P
表示,时空传输机用 #
表示,墙用 *
表示,平地用 .
表示。
骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。
骑士们在一层中只能前后左右移动,每移动一格花费 $1$ 时刻的时间。
层间的移动只能通过时空传输机,且不需要任何时间。
输入格式
输入的第一行 $C$ 表示共有 $C$ 个测试数据。
每个测试数据的前一行有三个整数 $N,M,T$。 $N,M$ 表示迷宫的大小为 $N \\times M$。
接下去的 $N$ 行,每行包含一个长度为 $M$ 的字符串表示迷宫的第一层的布置情况,
再接下去的 $N$ 行,每行包含一个长度为 $M$ 的字符串表示迷宫第二层的布置情况。
输出格式
每组数据输出一行答案,如果骑士们能够在 $T$ 时刻内找到公主就输出 YES
,否则输出 NO
。
数据范围
$1 \\le C \\le 100$,
$1 \\le N,M \\le 10$
输入样例:
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
输出样例:
YES
思路
- 用
bfs
解决.- 该题是三维空间,其次楼层只有两层,可将楼层设为$0$楼,$1$楼,方便传送时楼层的切换(可通过
异或操作
或者1-x
的操作($1-0=1$,$1-1=0$)实现),其次注意的是在判断移动到传送点的位置时,需要判断传送过去的那个点其是否为墙或者是否为传送,避免反复传送,死循环.
代码
// Problem: A计划
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4236/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-13 11:21:42
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 15
using namespace std;
typedef long long ll;
int t;
int n,m,times;
int vis[2][MAXN][MAXN];
char g[2][MAXN][MAXN];
struct node{
int x;
int y;
int z;
int step;
}girl;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int bfs()
{
queue<node> q;
q.push({0,0,0,0});
vis[0][0][0]=1;
while(q.size()>0)
{
node temp=q.front();
q.pop();
//cout << temp.x << " " << temp.y << " " << " " << temp.z << " " << temp.step << endl;
if(temp.x==girl.x&&temp.y==girl.y&&temp.z==girl.z)
{
if(temp.step<=times)
return 1;
else return 0;
}
for(int i=0;i<=3;i++)
{
int dz=temp.z,dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(g[dz][dx][dy]=='#')//传送(异或解决)
dz^=1;
//异或过去有可能是传送或者墙,需判掉当前可能传送过去的点也是传送点
if(dx<0||dx>=n||dy<0||dy>=m||g[dz][dx][dy]=='*'||g[dz][dx][dy]=='#')
continue;
if(vis[dz][dx][dy]==0)
{
q.push({dx,dy,dz,temp.step+1});
vis[dz][dx][dy]=1;
}
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
memset(vis,0,sizeof(vis));
cin >> n >> m >> times;
for(int i=0;i<=1;i++)
for(int j=0;j<=n-1;j++){
cin >> g[i][j];
for(int k=0;k<=m-1;k++)
if(g[i][j][k]=='P')
girl={j,k,i};
}
//cout << girl.x << " " << girl.y << " " << girl.z << endl;
if(bfs()==1)
cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}