Find largest area in 2d array in c++

Question

I need to write recursive function in c++ that finds largest area of number '1' in 2d array that contains only 1 or 0.

Example:

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, },
};

Visual example: http://s23.postimg.org/yabwp6h23/find_largest.png

Largest area of this array is 12, second largest is 3 and third largest is 2.

I was thinking to do this with something similar to flood fill algorithm, but just can't figure out how.

Answer 1

I was thinking to do this with something similar to flood fill algorithm

I think that's a pretty good way to do it. Apply flood fill to any 1, counting the ones and replacing them with zeros.

Repeat until the grid consists entirely of zeroes.

The following will print out the sizes of the connected components in no particular order:

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