文章目录
题目思路代码
题目
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。
INPUT:
输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N*M(1 -1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int sx, sy, sz, ex, ey, ez;
queue q;
bool noway(int x, int y, int z) {
if (x = M)
return true;
if (vis[z][x][y] == 1)
return true;
if (Map[z][x][y] == '*')
return true;
if (Map[z][x][y] == '#' && Map[!z][x][y] == '*')
return true;
return false;
}
bool BFS() {
Node head;
head.x = sx;
head.y = sy;
head.z = sz;
head.dept = 0;
vis[sz][sx][sy] = 1;
q.push(head);
while (!q.empty()) {
Node cur = q.front();
q.pop();
for (int i = 0; i
continue;
}
if (Map[nz][nx][ny] == '#') {
if (Map[!nz][nx][ny] == '#' || vis[!nz][nx][ny] == 1) {
vis[nz][nx][ny] = 1;
continue;
}
nz = !nz;
}
Node next;
next.x = nx;
next.y = ny;
next.z = nz;
next.dept = cur.dept + 1;
vis[nz][nx][ny] = 1;
if (nx == ex && ny == ey && nz == ez) {
if (next.dept
cin >> N >> M >> T;
memset(Map, 0, sizeof(Map));
memset(vis, 0, sizeof(vis));
for (int i = 0; i
for (int k = 0; k
sx = j;
sy = k;
sz = i;
}
if (Map[i][j][k] == 'P') {
ex = j;
ey = k;
ez = i;
}
}
}
}
if (BFS())
cout |