简答题 偏难
#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 &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;stdbool.h&gt; #include &lt;string.h&gt; #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 &amp;&amp; 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 &lt; rear) {         nd = q[front++];         x = nd.x;         y = nd.y;         if (x &lt; 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 &gt; 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 &lt; 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 &gt; 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", &amp;k);     while (k--) {         scanf("%d %d", &amp;m, &amp;t);         for (i = 0; i &lt; m; i++) {             for (j = 0; j &lt; m; j++) {                 scanf(" %c", &amp;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 &lt;= t &amp;&amp; ans &gt;= 0) {             printf("YES\n");         } else {             printf("NO\n");         }     }     return 0; }</pre>
这道题暂未补解析。