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.

Flood fill would work. If you get stuck somewhere, you should post your attempt and describe your problem. — Drew Dormann, Mar 29 '13 at 14:41
Maybe for each element that equals 1 check North, South East and West then increment and check again. Also, add incremented array indices to an ignore list. There are so many flood fill algorithms it would be interesting to know which is the best. — james82345, Mar 29 '13 at 14:49
a related question is http://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-nn-binary-matrix — Mihai8, Mar 29 '13 at 14:52

score 3 · Answer 1 · answered Mar 29 '13 at 15:21

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 :)

NPE · Accepted Answer · 2013-03-29T15:05:28.773

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

I'm not sure how you want to do this, but you have to be careful if you are replacing the `1`'s with `0`'s. Else you could cut one connected surface in two, and don't recognize anymore that they belonged together in the beginning. — Misch, Mar 29 '13 at 14:51

score 1 · Answer 3 · answered Mar 29 '13 at 14:53

something like,

int max_area = 0;

foreach y
    foreach x
        if (pos[y][x] == 1  &&  !visited[y][x])
        {
            int area = 0;
            Queue queue = new Queue();
            queue.push(new Point(x, y));
            visited[y][x] = true;

            while (!queue.empty())
            {
                Point pt = queue.pop();
                area++;

                foreach neightboor of pt (pt.x±1, pt.y±1)
                    if (pos[neightboor.y][neightboor.x] == 1  &&  !visited[neightboor.y][neightboor.x])
                    {
                        visited[neightboor.y][neightboor.x] = true;
                        queue.push(new Point(neightboor.x, neightboor.y));
                    }
            }

            if (area > max_area)
                max_area = area;
        }

BTW: OP was asking for recursive solution, so flood fill and backtracking together should work — taocp, Mar 29 '13 at 15:04

Jo So · Answer 4 · 2013-03-29T15:17:43.953

Quick approach, but I don't know if there is a way to do this in a sane way (recursive call for each element does not scale for C++ because call stack is limited)

int maxy = 5
int maxx = 8

int areasize(int x, int y) {
    if (x < 0 || y < 0 || x > maxx || y > maxy || !Arr[y][x])
        return 0;

    Arr[y][x] = 0;

    return 1
           + areasize(x + 1, y)
           + areasize(x - 1, y)
           + areasize(x, y + 1)
           + areasize(x, y - 1);
}

maxarea = 0;

for (int y = 0; y < maxy; y++) {
    for (int x = 0; x < maxx; x++) {
        maxarea = std::max(maxarea, areasize(x, y));
    }
}

Thanks for the hint, I forgot to insert the erase statement. — Jo So, Mar 29 '13 at 15:08

Find largest area in 2d array in c++

4 Answers4