C++ 数据结构之水洼的数量算法

问题描述

有一个矩阵区域，其中包含了若干个“水洼”，每个水洼是由相邻的“水滴”组成的区域。其中，相邻的“水滴”指的是上下左右四个方向上位置相邻的“.”，而不是斜对角线方向。

例如，下面的矩阵区域中，连续的“.”就构成了两个水洼：

X . . X .
X . . X .
. X X . .
. . . X .

现在，给定一个这样的矩阵，编写一个程序，计算其中的水洼数量。

解题思路

本题的基本思路是：遍历矩阵中的每个位置，如果当前位置是“.”并且还没有被访问过，就从该位置开始进行深度优先搜索（DFS），找到与该位置相邻且为“.”的所有位置，将它们标记为已经访问过，并继续向下进行DFS。最终，每次对未访问过的“.”进行DFS就可以找到一个新的水洼，最终得到的DFS深度总数就是水洼的大小。

// 定义矩阵大小
#define MAXN 1001

// 定义矩阵和标记数组
char mat[MAXN][MAXN];
bool vis[MAXN][MAXN];

// DFS函数进行搜索，并标记已经访问过的位置
void dfs(int x, int y) {
    // 标记当前位置为已经访问过
    vis[x][y] = true;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for(int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        // 判断是否越界或者不是水洼
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && mat[nx][ny] == '.'&& !vis[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    // 读入矩阵的大小和矩阵本身
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%s", mat[i]);
    }
    // 初始化标记数组
    memset(vis, false, sizeof(vis));
    int count = 0;
    // 遍历每个位置
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            // 如果是 "." 并且还没有被遍历过，就进行DFS
            if(mat[i][j] == '.' && !vis[i][j]) {
                count++; // 计数器加1
                dfs(i, j);
            }
        }
    }
    printf("%d\n", count); // 输出水洼的数量
    return 0;
}

其中，mat数组表示矩阵，它的每一行对应一个字符串，而每个字符串中的每个字符表示该位置上的“水滴”或者其他障碍物。vis数组表示标记数组，它表示每个位置是否已经被遍历过。

下面是两个具体的例子。

示例说明

示例 1

4 5
X . . X .
X . . X .
. X X . .
. . . X .

输入以上矩阵后，程序应该输出：

2

这是因为该矩阵中包含两个水洼。

示例 2

3 3
. . .
. . .
. . .

输入以上矩阵后，程序应该输出：

0

这是因为该矩阵中没有水洼。