2022 年 6 月青少年软编等考 C 语言五级真题解析

Source

T1. 逃离迷宫

你在一个地下迷宫中找到了宝藏，但是也触发了迷宫机关，导致迷宫将在 $T$ 分钟后坍塌，为此你需要在 $T$ 分钟内逃离迷宫，你想知道你能不能逃离迷宫。迷宫是一个边长为 $m$ 的正方形，其中 S 表示你所在的位置，E 表示迷宫出口，. 是可以随意走动的区域，# 是不可穿行的墙壁，每次你可以耗费 $1$ 分钟在区域间移动（上下左右四个方向）。

时间限制：1 s
内存限制：64 MB

输入
输入包含多组数组，第一行是一个整数 $K$ （ $\le K \le 10$ )，表示有 $K$ 组数据。接下来每组数组包含整数 $m\ (2\le m\le 10)$ 和整数 $T$ ， $m$ 表示正方形迷宫的边长， $T$ 表示坍塌时间。其后是一个 $m\times m$ 的字符矩阵，包含字符 S，E，. 和 #。
输出
每组数据输出一行，输出 YES 或者 NO，表示是否可以在坍塌之前逃离（也就是说移动次数是否可以不超过 $T$ ）。

样例输入

2
4 7 
S...
###.
.#E.
..#.
3 4
S..
..#
.#E

样例输出
```
YES
NO
```

思路分析

此题考查 $\tt BFS$ ，属于模板题。

从起点开始进行 $\tt BFS$ ，如果找到了终点，则检测花费的时间是否不超过 $T$ ，如果是，则可以逃离；否则不可逃离，因为 $\tt BFS$ 找出的是最短时间。如果没有找到终点，则不可逃离。

/*
 * Name: T1.cpp
 * Problem: 逃离迷宫
 * Author: Teacher Gao.
 * Date&Time: 2025/02/08 08:34
 */

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

int dx[] = {
   
    
      1, 0, -1, 0};
int dy[] = {
   
    
      0, 1, 0, -1};

int m, T;
char a[15][15];
int dis[15][15];
deque<int> Q;

bool BFS() {
   
    
      
    while (!Q.empty()) {
   
    
      
        int x = Q.front(); Q.pop_front();
        int y = Q.front(); Q.pop_front();

        if (a[x][y] == 'E') {
   
    
      
            return dis[x][y] <= T;
        }

        for (int i = 0; i < 4; i++) {
   
    
      
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > m || ny < 1 || ny > m) continue;
            if (a[nx][ny] == '#' || dis[nx][ny] != -1) continue;

            dis[nx][ny] = dis[x][y] + 1;
            Q.push_back(nx);
            Q.push_back(ny

目录

T1. 逃离迷宫

思路分析