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

T1. 走迷宫

题目链接：SOJ D1233

一个迷宫由 $R$ 行 $C$ 列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角最少需要走多少步（数据保证一定能走到）。只能在水平方向或垂直方向走，不能斜着走。

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

• 输入
  第一行是两个整数 $R$ 和 $C$（$1\le R,C\le 40$）。
  接下来是 $R$ 行，每行 $C$ 个字符，代表整个迷宫。空地格子用 . 表示，有障碍物的格子用 # 表示。迷宫左上角和右下角都是 .。
• 输出
  输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
• 样例输入

  5 5
  ..###
  #....
  #.#.#
  #.#.#
  #.#...
  

• 样例输出

  9
  

思路分析

此题考查洪水填充算法中的 $\mathtt{BFS}$，为 2023 年 12 月五级第四题数据弱化版，见 2023 年 12 月青少年软编等考 C 语言五级真题解析中的 T4。属于模板题，此处不再赘述。

/*
 * Name: T1.cpp
 * Problem: 走迷宫
 * Author: Teacher Gao.
 * Date&Time: 2025/07/10 19:52
 */

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

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

int R, C;
char g[45][45];
int dis[45][45];

void BFS(int sx, int sy) {
   
    queue<int> Q;
    Q.push(sx); Q.push(sy);
    memset(dis, 0, sizeof(dis));
    while (!Q.empty()) {
   
        int x = Q.front(); Q.pop();
        int y = Q.front(); Q.pop();
        
        if (x == R && y == C) {
   
            cout << dis[x][y] << "\n";
            return ;
        }

        for (int i = 0; i < 4; i++) {
   
            int nx = x + dx[i], ny = y + dy[i];

            if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
            if (g[nx][ny] == '#' || dis[nx][ny]) continue;

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

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> R >> C;
    for (int i = 1; i <= R; i++)