B4474 [厦门小学生 C++ 2025] 故障机器人

题目描述

有一个网格，由 $n$ 行和 $m$ 列组成。网格的每个单元格要么是空的，要么是一堵墙。其中有一个空单元内有一个实验室。网格边界外全部是墙。

一个故障机器人从一个实验室逃了出来。它目前在网格的某个空单元中。你可以向机器人发送以下命令之一：“向右移动”、“向下移动”、“向左移动”或“向上移动”。每个命令意味着移动到相应方向的相邻单元格。

然而，由于机器人故障了，除了听从命令，它什么都会做。收到命令后，它将选择一个与命令方向不同的可通行的方向。如果找不到不听指令的移动方法，那么它什么都不做。

我们想让机器人到达实验室从而可以修理它。对于每个空单元，确定机器人是否可以从该单元开始到达实验室。也就是说，在机器人的每一步之后，都可以向机器人发送一个命令，使得无论机器人选择什么方向，它最终都能进入实验室。

输入格式

本题有多组数据。

第一行包含一个整数 $T$，表示数据组数。

每个测试样例的第一行包含两个整数 $n$ 和 $m$，表示网格中的行数和列数。

接下来有 $n$ 行，每行表示网格的一行，包括 $m$ 个 $C_{i,j}$ 字符。包括以下三种类型之一：

• . — 单元格是空的；
• # — 单元格被阻塞；
• L — 单元格内有一个实验室。

题目保证网格仅包含一个实验室。

输出格式

对于每个测试样例，找到可以使机器人到达实验室的空格。对于原网格图，将可以到达实验室的空格替换为加号 (+)，打印新的网格。

输入输出样例 #1

输入 #1

4
3 3
...
.L.
...
4 5
#....
..##L
...#.
.....
1 1
L
1 9
....L..#.

输出 #1

...
.L.
... 
#++++
..##L
...#+
...++
L
++++L++#.

说明/提示

【样例解释】

在第一个测试样例中，没有可以使机器人到达实验室的空格。考虑一个角空格。给定任何方向，它将移动到相邻的边界空格。现在考虑一个非角空格。无论你向机器人发送什么方向，它都可以选择不同的方向，这样它就会走回角落里。

在最后一个测试样例中，您可以继续向机器人发送与实验室方向相反的命令，机器人将别无选择，只能向实验室移动。

【数据范围】

对于 $20\%$ 的数据：$1\le T\le 10,1\le n,m\le 10$；

对于另外 $20\%$ 的数据：$n,m$ 至少有一个为 $1$；

对于 $100\%$ 的数据：$1\le T\le 10000,1\le n,m\le 10^6$，且对于 $T$ 组样例中 $n\times m$ 的总和小于等于 $10^6$。$C_{ij}$ 属于 {.,#,L}\{\tt{., \#, L}\}{.,#,L}，且有且仅有一个 $C_{ij}=\mathtt{L}$。

C++实现

#include<bits/stdc++.h>
using namespace std;
struct node {int x, y;};
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int main() {
    int T;
    cin >> T;
    while(T--) {
        int n, m, sx, sy;
        queue <node> q;
        cin >> n >> m;
        const int N = n, M = m;
        char c[N + 5][M + 5];
        memset(c, '#', sizeof c);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cin >> c[i][j];
                if(c[i][j] == 'L') sx = i, sy = j, c[i][j] = '#';
            }
        }
        q.push({sx, sy});
        while(q.size()) {
            int lx = q.front().x, ly = q.front().y;
            q.pop();
            for(int i = 0; i <= 3; i++) {
                int nx = lx + dx[i], ny = ly + dy[i];
                if(c[nx][ny] == '.') {
                    int num = 0;
                    for(int j = 0; j <= 3; j++) 
                        if(c[nx + dx[j]][ny + dy[j]] == '.' || c[nx + dx[j]][ny + dy[j]] == 'L') num++;
                    if(num <= 1) {
                        c[nx][ny] = '+';
                        q.push({nx, ny});
                    }
                }
            }
        }
        c[sx][sy] = 'L';
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) cout << c[i][j];
            cout << '\n';
        }
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容