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

bool visited[5][8];
int i,j;
// variables for the area:
int current_area = 0, max_area = 0;
int Arr[5][8]={ // type your map of values here
}

// functions

void prepare_visited_map() {
    for(i=0;i<5;i++) {
        for(j=0;j<8;j++) visited[i][j] = false;
    }
}

// recursive function to calculate the area around (x,y)
void calculate_largest_area(int x, int y) {
    if(visited[x][y]) return;
    // check if out of boundaries
    if(x<0 || y<0 || x>=5 || y>=8) return;
    // check if the cell is 0
    if(!Arr[x][y]) {
        visited[x][y] = true;
        return;
    }

    // found a propper cell, proceed
    current_area++;
    visited[x][y] = true;
    // call recursive function for the adjacent cells (north, east, south, west)
    calculate_largest_area(x,y-1);
    calculate_largest_area(x+1,y);
    calculate_largest_area(x,y+1);
    calculate_largest_area(x-1,y);
    // by the end of the recursion current_area will hold the area around the initial    cell
}

// main procedure where the above functions are used
int mian() {
    // calculate the sorrounding area of each cell, and pick up the largest of all results
    for(i=0;i<5;i++) {
        for(j=0;j<8;j++) {
            prepare_visited_map();
            calculate_largest_area(i,j);
            if(current_area > max_area)   max_area = current_area;
        }
    }
    printf("Max area is %d",max_area");
}

Hope this was helpful :)

Answer 2

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