CODEWITHSUNDEEP
c++algorithmsearchmatrix
Buradi
Buradi

Reputation: 61

How to search an area of the same values in a matrix?

I have a matrix of integers like this:

1 1 1 0 3 3 3 0 2 2
1 1 1 0 3 3 3 0 2 2
0 0 0 0 3 3 3 0 0 0 
2 2 0 0 3 3 3 0 4 4
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 4 4 4 0

where I have different areas of the same value that are separated by "0"s and I need to count how many areas are in the matrix. My algorithm is based on the "0"s and every time a "0" is found a new area is about to come so I increment the counter. The problem is that I search row by row and enter the same area more than once. I only need to count the rectangular areas.

Upvotes: 3

Views: 1057

Answers (4)

Potatoswatter
Potatoswatter

Reputation: 137840

One simple, fast algorithm is to iterate over all entries and set each region to zeroes when it is encountered. This takes O(N*M) runtime (each entry visited at most twice) and O(1) additional memory.

To set a region to zeroes, just note the column where it begins, then iterate to the rightmost column. Then iterate over the rows below from the left to right columns, setting each entry to zero.

Working code:

int count_regions( int *arr, int rows, int cols ) {
    int region_count = 0;

    for ( int first_index = 0; first_index != rows * cols; ++ first_index ) {
        if ( arr[ first_index ] == 0 ) continue;

        ++ region_count;

        int first_row = first_index / cols, first_col = first_index % cols;
        int last_col;
        for ( last_col = first_col;
              last_col != cols && arr[ first_row * cols + last_col ] != 0;
              ++ last_col ) ;

        for ( int last_row = first_row; 
              last_row != rows && arr[ last_row * cols + first_col ] != 0;
              ++ last_row ) {
            for ( int col = first_col; col != last_col; ++ col ) {
                arr[ last_row * cols + col ] = 0;
            }
        }
    }
    return region_count;
}

Upvotes: 4

paddy
paddy

Reputation: 63481

I always liked the Union/Find algorithm for isolating groups. But that's cos I had an old implementation kicking around that I had written years ago. It's not a big deal to implement, but it might be more appropriate to use Flood Fill.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726659

One way is to use the Flood Fill algorithm to detect contiguous areas, like this:

Assuming that the initial matrix has only positive numbers,

  • Prepare a counter, set it to -1
  • For each point in the matrix:
  • If the cell is zero or negative, skip it; otherwise
  • Flood fill starting at the cell with the negative value of the counter
  • Decrement the counter after the flood fill is over

When you reach the end of your matrix, counter will have the negative number equal to the number of contiguous numbered areas minus one, i.e. the result that you need is -(counter+1).

Upvotes: 1

Mel Nicholson
Mel Nicholson

Reputation: 3225

The painting technique works well. The idea is that you drop a paint bomb that completely covers an area. Pseudocode:

for (each space) {
  if (space has been painted or is a border) continue;
  else {
    numAreas++;
    drop paint bomb
  }
}

And a paint bomb works like this:

paint space;
for (each adjacent space) {
  if (space has been painted or space is a border) continue;
  else {
    paint space;
    drop another bomb;
  }
}

Upvotes: 2

Related Questions