徐州网站开发设计平台,企业邮箱注册域名,专业免费网站建设一般多少钱,有经验的南昌网站制作题干#xff1a;
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后#xff0c;而今#xff0c;不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主#xff0c;因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚#xff0c;告招天下…题干
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后而今不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚告招天下勇士来拯救公主。不过公主早已习以为常她深信智勇的骑士LJ肯定能将她救出。 现据密探所报公主被关在一个两层的迷宫里迷宫的入口是S000公主的位置用P表示时空传输机用#表示墙用*表示平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置但如果被转到的位置是墙的话那骑士们就会被撞死。骑士们在一层中只能前后左右移动每移动一格花1时刻。层间的移动只能通过时空传输机且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据每个测试数据的前一行有三个整数NMT。 NM迷宫的大小N*M1 N,M 10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#...*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
解题报告 简单的bfs只是需要判断一下两层的对应位置上都是 # 这种特殊情况就可以了。这种情况不加的话会wa的。
AC代码
#includecstdio
#includequeue
#includecstring
#includecmath
#includemap
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
struct Node {int x,y;int t;int deep;Node(){}Node(int deep,int x,int y,int t):deep(deep),x(x),y(y),t(t){}
};
int n,m,k;
bool vis[2][15][15];//0表示第一层1表示第二层
char maze[2][15][15];
int nx[4] {0,1,0,-1};
int ny[4] {1,0,-1,0};
bool bfs() {memset(vis,0,sizeof(vis)); queueNode q;q.push((Node(0,1,1,0)));vis[0][1][1]1;Node cur; while(q.size()) {cur q.front();q.pop();if(maze[cur.deep][cur.x][cur.y] P) {if(cur.t k) return 1;else return 0;}int tx,ty;for(int i 0; i4; i) {tx cur.xnx[i];ty cur.yny[i];if(maze[cur.deep][tx][ty] * || vis[cur.deep][tx][ty] 1) continue;if(tx 1 || tx n || ty 1 || ty m) continue;vis[cur.deep][tx][ty] 1;if(maze[cur.deep][tx][ty] # maze[!cur.deep][tx][ty] ! * vis[!cur.deep][tx][ty] 0) {vis[!cur.deep][tx][ty] 1;q.push(Node(!cur.deep,tx,ty,cur.t1));}else if(maze[cur.deep][tx][ty]. || maze[cur.deep][tx][ty]P) {q.push(Node(cur.deep,tx,ty,cur.t1));}}}return 0;
}
int main()
{int t;cint;while(t--) {scanf(%d%d%d,n,m,k);for(int i 1; in; i) {scanf(%s,maze[0][i]1);}for(int i 1; in; i) {scanf(%s,maze[1][i]1);}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[0][i][j] # maze[1][i][j] #) {maze[0][i][j] maze[1][i][j] *;}}}if(bfs()) printf(YES\n);else printf(NO\n);}return 0 ;
}
