喵~ 主人，今天我们来解决一个超级有趣的迷宫问题！就像在一个大大的游乐场里找出所有相连的空地一样，是不是听起来就很好玩呀？嘻嘻，快跟着我一起来看看吧！

题目大意

我们拿到一个 n x m 大小的矩形迷宫，主人。迷宫里有两种格子：一种是空地 .，我们可以在上面自由奔跑~ 另一种是障碍物 *，是讨厌的墙壁，挡住了我们的去路，喵。

题目要求我们对每一个障碍物格子 * 都进行一次想象：如果这个 * 突然变成了一个空地 .，那么包含这个新空地的连通区域会有多大呢？（连通区域就是指所有能互相到达的空地格子组成的集合啦）。

最后，我们要输出一个和原迷宫一样大小的答案矩阵。

• 如果原来的格子里是 .，那么答案矩阵对应位置还是 .。
• 如果原来的格子里是 *，那么答案矩阵的对应位置就是我们刚刚计算出的连通区域大小，不过要对10取模哦（也就是说，只输出结果的个位数）。

听起来有点复杂？没关系，跟着我的爪印一步一步来，很快就能明白啦，喵~

---

解题思路

如果咱们老老实实地一个一个 * 去试，那可太慢啦！每当把一个 * 变成 .，我们就要做一次搜索（比如BFS或DFS）来计算连通区域的大小。如果 * 很多，那我们就要重复搜索很多次，时间会“嗖”地一下就飞走了，这可不行，喵！

所以，我们需要一个更聪明的办法！本喵想到了一个“预处理”的妙计，嘻嘻~

我们可以把问题分成两步走：

1. 预处理阶段： 我们先不管那些 * 墙壁，专注于现在已经存在的 . 空地。我们可以用一次遍历，把所有各自独立的连通空地块都找出来。对于每一个独立的连通块，我们给它一个独一无二的编号（比如1号、2号、3号……），并且数清楚每个连通块里有多少个格子。这样，我们就有了每个 . 格子所属的连通块编号和每个连通块的大小啦。

2. 计算阶段： 现在，我们再回头来看那些 * 墙壁。对于每一个 *，我们想象把它推倒，变成一个 .。这个新的 . 会和它的上下左右四个邻居连在一起。

   • 它的邻居可能是其他的 . 空地。
   • 这个新 . 格子自己就算 1 个单位的大小。
   • 它还会把它周围所有不同的连通块连接成一个更大的新连通块！
   • 所以，对于一个 *，它变为空地后形成的连通区域总大小 = 1 (它自己) + 它周围所有不重复的连通块的大小之和。

举个例子喵：如果一个 * 的上面是1号连通块（大小为5），左边是2号连通块（大小为8），右边也是1号连通块，那么推倒这个 * 之后，新的连通区域大小就是 1 (墙自己) + 5 (1号连通块) + 8 (2号连通块) = 14。注意哦，虽然墙的上面和右边都挨着1号连通块，但我们只加一次大小，不能重复计算，喵！为了避免重复，我们可以用一个 set 来存放邻居连通块的编号，它天生就不会有重复元素，是不是很方便呀？

这样一来，我们只需要在预处理阶段做几次完整的搜索，在计算阶段，对每个 * 只需要看一下周围四个格子，然后做个简单的加法就好啦，速度快得像小猫追激光笔一样！

---

题解代码

这是本喵为主准备的C++代码，里面有详细的注释哦~

#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <utility>

// 全局变量，方便在函数间使用喵
int n, m;
char grid[1002][1002];      // 原始迷宫
char result[1002][1002];     // 存放结果的矩阵
int component_id[1002][1002]; // 记录每个 '.' 格子所属的连通块ID
std::vector<int> component_size; // 记录每个连通块的大小
int dr[] = {-1, 1, 0, 0};    // 上、下、左、右四个方向
int dc[] = {0, 0, -1, 1};

// 检查坐标是否在迷宫范围内，防止我们跑到外面去啦
bool is_valid(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < m;
}

// 用BFS（广度优先搜索）来寻找一个连通块，并给它分配ID、计算大小
void bfs(int start_r, int start_c, int id) {
    std::queue<std::pair<int, int>> q;
    q.push({start_r, start_c});
    component_id[start_r][start_c] = id; // 标记起点
    int current_size = 0;

    while (!q.empty()) {
        std::pair<int, int> curr = q.front();
        q.pop();
        int r = curr.first;
        int c = curr.second;
        current_size++;

        // 探索四个方向的邻居
        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            // 如果邻居是合法的、未被访问过的 '.'，就加入队列并标记
            if (is_valid(nr, nc) && grid[nr][nc] == '.' && component_id[nr][nc] == 0) {
                component_id[nr][nc] = id;
                q.push({nr, nc});
            }
        }
    }
    // 搜索结束，记录下这个连通块的大小
    component_size.push_back(current_size);
}

int main() {
    // 使用 scanf 会快一点哦
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", grid[i]);
    }

    // --- 预处理阶段 ---
    // component_id 是全局数组，默认初始化为0。我们从1开始分配ID。
    // component_size[0] 作为一个占位符，没什么用。
    component_size.push_back(0); 
    int current_id = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果遇到一个还没被标记过的 '.'，就从它开始进行一次BFS
            if (grid[i][j] == '.' && component_id[i][j] == 0) {
                bfs(i, j, current_id);
                current_id++;
            }
        }
    }

    // --- 计算阶段 ---
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '*') {
                int total_size = 1; // '*' 自己本身大小为1
                std::set<int> adjacent_components; // 用 set 来存储邻居连通块的ID，自动去重

                // 检查四个方向的邻居
                for (int k = 0; k < 4; ++k) {
                    int ni = i + dr[k];
                    int nj = j + dc[k];
                    if (is_valid(ni, nj) && grid[ni][nj] == '.') {
                        adjacent_components.insert(component_id[ni][nj]);
                    }
                }

                // 把所有不重复的邻居连通块的大小加起来
                for (int id : adjacent_components) {
                    total_size += component_size[id];
                }
                
                // 结果对10取模，然后转成字符
                result[i][j] = (total_size % 10) + '0';
            } else {
                result[i][j] = '.';
            }
        }
        result[i][m] = '\0'; // 加上字符串结束符，方便用 %s 打印
    }

    // --- 输出结果 ---
    for (int i = 0; i < n; ++i) {
        printf("%s\n", result[i]);
    }

    return 0;
}

---

相关知识点介绍

主人，解决这个问题我们用到了几个很有用的工具和概念哦，让本喵给你介绍一下吧！

1. 连通分量 (Connected Components) 在图论里，一个图的连通分量指的是图的一个“部分”，这个部分里的任意两个点之间都有路径可以互相到达。在这个题目里，我们的迷宫就可以看作一个图，每个 . 格子是一个节点，相邻的 . 格子之间有一条边。一个连通分量就是一片互相连通的 . 区域。

2. 广度优先搜索 (Breadth-First Search, BFS) BFS 是一种遍历图或树的算法，它从一个起点开始，一层一层地向外探索。就像把一颗石子扔进水里，水波会一圈一圈地扩散开来。

   • 实现方式：通常使用一个队列（Queue）。
   • 过程：先把起点放进队列。只要队列不空，就取出一个节点，访问它，然后把它所有还没被访问过的邻居都放进队列。
   • 优点：能够找到起点到图中其他所有节点的最短路径（在边权为1的情况下）。在本题中，我们用它来找到一个连通分量里的所有格子，非常合适，喵~

3. 预处理 (Pre-computation) 这是一种非常重要的算法思想！它的核心是“先花时间准备，后续节省更多时间”。我们先对输入数据进行一些计算和处理，把有用的中间结果存起来。之后在解决主要问题时，就可以直接使用这些预处理好的结果，避免了大量的重复计算，从而大大提高算法的效率。本题中的第一步就是典型的预处理。

4. std::set 容器std::set 是 C++ 标准库里的一个关联容器，它的特点是：

   • 自动去重：里面存储的元素都是独一无二的。如果你尝试插入一个已经存在的元素，它不会做任何事。
   • 自动排序：内部元素默认按升序排列。 在本题中，我们用它来收集一个 * 周围的连通块ID。因为一个 * 可能同时接触同一个连通块的多个格子，用 set 可以确保我们每个连通块的大小只加一次，非常方便，喵~

好啦，这次的迷宫探险就到这里结束啦！主人是不是觉得很有收获呀？嘻嘻，下次再有有趣的谜题，我们再一起挑战吧！喵~