简答题
偏难
#7191
逃离迷宫 你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为…
逃离迷宫
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。
时间限制:1000
内存限制:65536
输入
输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。
输出
每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。
样例输入
2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E
样例输出
YES NO
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
struct node {
int x, y;
int tcnt;
};
int m, t;
char mat[MAX_M][MAX_M];
int bfs(int x0, int y0, int x1, int y1) {
if (x0 == x1 && y0 == y1) {
return 0;
}
struct node nd = {x0, y0, 0};
int x, y;
struct node q[MAX_M * MAX_M];
int front = 0, rear = 0;
q[rear++] = nd;
while (front < rear) {
nd = q[front++];
x = nd.x;
y = nd.y;
if (x < m - 1) {
if (mat[x + 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x + 1][y] == '.') {
struct node newNode = {x + 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x + 1][y] = '*';
}
}
if (x > 0) {
if (mat[x - 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x - 1][y] == '.') {
struct node newNode = {x - 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x - 1][y] = '*';
}
}
if (y < m - 1) {
if (mat[x][y + 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y + 1] == '.') {
struct node newNode = {x, y + 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y + 1] = '*';
}
}
if (y > 0) {
if (mat[x][y - 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y - 1] == '.') {
struct node newNode = {x, y - 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y - 1] = '*';
}
}
}
return -1;
}
int main() {
int k, i, j, x0, y0, x1, y1, ans;
scanf("%d", &k);
while (k--) {
scanf("%d %d", &m, &t);
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
scanf(" %c", &mat[i][j]);
if (mat[i][j] == 'S') {
x0 = i;
y0 = j;
} else if (mat[i][j] == 'E') {
x1 = i;
y1 = j;
}
}
}
ans = bfs(x0, y0, x1, y1);
if (ans <= t && ans >= 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}</pre>
这道题暂未补解析。