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
这是因为该矩阵中没有水洼。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++ 数据结构之水洼的数量算法 - Python技术站