题目 数水坑 填涂颜色 细胞 南方小土豆 红与黑
数水坑
题目分析
题目给出了一个 N×MN \times MN×M 的网格，其中每个格子可能是水坑（'W'）或者是旱地（'.'）。我们需要统计网格中有多少个水坑。水坑定义为一组相邻的 'W' 组成的区域，并且相邻的格子可以是上下左右和四个对角线的方向。
解题思路
这是一个经典的图的连通块问题。
1. DFS 思路：
* 从网格中的每个 'W' 开始进行深度优先搜索，标记这个水坑区域中的所有 'W' 为已访问（例如，可以将它们改为 '.'），避免重复计数。
* 每发现一个 'W'，就启动一次 DFS 搜索，并增加水坑的计数。
* 通过 DFS 可以在找到一个 'W' 时，递归地探索其相邻的八个格子（上下左右及四个对角线）。
2. 边界判断：
* 需要确保 DFS 过程中，每次访问的点都在网格内，避免访问越界。
3. 时间复杂度：
* 时间复杂度为 O(N×M)O(N \times M)O(N×M)，每个格子最多被访问一次，DFS 的递归深度与网格大小成正比。
代码实现
填涂颜色
题目分析
给定一个 n×nn \times nn×n 的矩阵，其中包含数字 0 和 1，我们需要根据要求将其中的“闭合圈”内部的 0 填充成 2。闭合圈由 1 构成，围住了一部分 0。我们需要找到这些被 1 围住的 0，并将它们填涂为 2。
思路：
* 首先，需要找到矩阵边缘的 0，这些 0 是与外部空地连接的，应该保持不变。通过深度优先搜索（DFS）或广度优先搜索（BFS）可以标记所有与边缘相连的 0。
* 接下来，将剩余的 0 视为被围住的 0，将这些 0 填充为 2。
解题步骤
1. 遍历矩阵边缘：从矩阵的边缘开始，找到所有与边缘连接的 0，并用 DFS 将它们标记为已访问。
2. 处理内部 0：对于没有被标记的 0，它们就被 1 围住，应该填涂为 2。
3. 输出最终矩阵：将矩阵按照填涂规则输出。
关键点
* DFS 递归：通过 DFS 从矩阵边缘开始递归遍历所有与边缘连接的 0。
* 时间复杂度：由于每个节点最多被访问一次，DFS 的时间复杂度为 O(n2)O(n^2)O(n2)，适用于最大矩阵尺寸 30×3030 \times 3030×30。
代码实现
细胞
题目描述
给定一个矩形阵列，其中每个位置有一个数字 0 到 9，其中 1 到 9 代表细胞。细胞是指在矩阵中，沿着上下左右相连的细胞数字形成的区域。我们需要求出该矩阵中细胞的个数。
输入格式
* 第一行输入两个整数 n 和 m，分别表示矩阵的行数和列数。
* 接下来有 n 行，每行有 m 个数字，表示矩阵的每个元素。
输出格式
* 输出一个整数，表示矩阵中的细胞个数。
思路分析
1. 问题本质
* 本题是一个典型的 联通区域计数问题，与“岛屿问题”类似。每个细胞由一个数字的区域组成，且细胞之间相连的条件是上下左右相邻且数字相同。
* 我们可以使用 DFS（深度优先搜索） 或 BFS（广度优先搜索） 来遍历每一个细胞，找到每一个连通的细胞区域，并统计数量。
2. 解题步骤
1. 构造矩阵：根据输入构造一个 n x m 的矩阵，标记每个位置的值。
2. DFS 遍历：我们可以用 DFS 从一个细胞数字（数字 1 到 9）开始，递归遍历该细胞区域内的所有相邻细胞，标记已访问的细胞，避免重复计算。
3. 计数细胞：每次遇到一个未访问的细胞时，执行一次 DFS，计数细胞数量。
3. 细节
* 确保处理矩阵的边界，防止访问越界。
* 需要维护一个访问标记，避免重复访问已遍历的细胞。
算法实现
1. DFS 搜索：从每个未访问的细胞出发，递归标记所有相邻的同一细胞区域。
2. 时间复杂度：每个细胞最多被访问一次，DFS 的时间复杂度为 O(n×m)O(n \times m)O(n×m)，适合本题的输入限制。
代码实现
南方小土豆
题目描述
给定一个 N x M 的矩阵，每个位置的数字代表一种农作物（1 到 9）。数字相同的农作物在矩阵中如果相连，则视为同一块。要求计算每种农作物有多少块连通区域。区域是上下左右相邻的相同数字构成的。
输入格式
* 第一行输入两个整数 N 和 M，分别表示矩阵的行数和列数。
* 接下来的 N 行，每行包含 M 个数字，表示每个网格的内容。
输出格式
输出一行，包含 9 个整数，每个整数代表对应农作物的块数（从 1 到 9）。
思路分析
1. DFS/DFS 搜索
* 题目本质是图的联通块计数问题。每一块农作物可以看作是一个连通的区域，矩阵中相同数字的上下左右相邻部分是同一块农作物。
* 我们可以使用 深度优先搜索（DFS） 来遍历这些区域。通过遍历每一个未访问过的细胞，将其标记为已访问，并递归地遍历其四个方向的相邻细胞，直到所有相连的区域都被标记。
2. 步骤
1. 构建矩阵：根据输入数据构建矩阵。
2. DFS 遍历：从每一个未访问过的农作物开始执行 DFS，标记并统计每块农作物区域。
3. 输出结果：最后输出每种农作物的块数。
3. 注意点
* DFS 中需要确保不越界，且只有当该位置的数字和当前农作物相同且未访问时，才继续递归。
* 通过二维数组来存储每个位置的访问状态，避免重复访问。
代码实现
红与黑
题目描述
给定一个长方形的房间，地面上铺有红色（'R'）和黑色（'B'）的瓷砖，你从一个特殊的黑色瓷砖（'@'）出发，要求计算你能够到达多少块黑色瓷砖。你只能在相邻的黑色瓷砖之间移动。相邻是指上下左右四个方向。
输入格式
* 第一行输入两个整数 n 和 m，表示房间的行数和列数。
* 接下来是 n 行，每行 m 个字符，表示房间的瓷砖颜色，其中：
* 'B' 表示黑色瓷砖。
* 'R' 表示红色瓷砖。
* '@' 表示黑色瓷砖，并且你站在这块瓷砖上，且唯一出现一次。
输出格式
输出一个整数，表示你从初始位置出发能够到达的黑色瓷砖数（包括起始瓷砖）。
思路分析
这题的核心是图的连通性问题。可以将问题建模为一个矩阵，求出从起始位置 '@' 开始，通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历所有相连的黑色瓷砖的数量。
1. DFS 遍历
* 我们可以使用 深度优先搜索（DFS） 来遍历从起始位置 '@' 出发，能够到达的所有相连的黑色瓷砖。
* 通过递归的方式，探索每个相邻的黑色瓷砖，直到所有可以到达的瓷砖都被访问。
2. 步骤
1. 输入矩阵：根据输入数据构建矩阵，找到起始位置 '@'。
2. DFS 遍历：从起始位置出发，递归地访问所有与其相连的黑色瓷砖。
3. 输出结果：最终输出能够到达的黑色瓷砖数量。
代码实现
