我考虑使用类似泛洪填充算法的方式来实现这个功能。
我认为这是一个很好的方法。对于任何一个数字为1的位置应用泛洪填充算法,计数并将它们替换为0。
重复此过程,直到网格完全由0组成。
以下内容将无特定顺序地打印出连接组件的大小:
#include <iostream>
constexpr int N = 5;
constexpr int M = 8;
int arr[N][M] =
{
{ 0, 0, 0, 0, 1, 1, 0, 0, },
{ 1, 0, 0, 1, 1, 1, 0, 0, },
{ 1, 1, 0, 1, 0, 1, 1, 0, },
{ 0, 0, 0, 1, 1, 1, 1, 0, },
{ 0, 1, 1, 0, 0, 0, 0, 0, },
};
int fill(int arr[N][M], int r, int c) {
int count = 0;
if (r < N && arr[r][c]) {
for (int i = c; i >= 0 && arr[r][i]; --i) {
arr[r][i] = 0;
count += fill(arr, r + 1, i) + 1;
}
for (int i = c + 1; i < M && arr[r][i]; ++i) {
arr[r][i] = 0;
count += fill(arr, r + 1, i) + 1;
}
}
return count;
}
int print_components(int arr[N][M]) {
for (int r = 0; r < N; ++r) {
for (int c = 0; c < M; ++c) {
if (arr[r][c]) {
std::cout << fill(arr, r, c) << std::endl;
}
}
}
}
int main() {
print_components(arr);
}