c++ - 在C++中找到2D数组中的最大面积

我需要在C++中编写递归函数，该函数在仅包含1或0的2d数组中找到数字“1”的最大区域。

例子:

int Arr[5][8] =
{
{ 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, },
};

可视示例:http://s23.postimg.org/yabwp6h23/find_largest.png

该阵列的最大面积是12，第二大面积是3，第三大面积是2。

我当时想用类似于洪水填充算法的方法来做到这一点，但是却不知道该怎么做。

最佳答案

我认为这是一个很好的方法。将泛洪填充应用于任何1，将其计数并用零替换。

重复直到网格完全由零组成。

以下内容将以不特定的顺序打印连接的组件的尺寸:

#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);
}

关于c++ - 在C++中找到2D数组中的最大面积，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15705490/