CODEWITHSUNDEEP
calgorithmmatrixmultidimensional-array
imre
imre

Reputation: 489

Looking up squares in matrices

I'm having trouble coming up with an algorithm to go through a matrix made of zeroes and ones, which e.g. looks like this:

3 5
1 0 1 1 1
0 0 1 0 1
0 0 1 1 1

The first two digits are the number of rows and columns. Zeroes are whitespace, ones are actual "lines". I know that to go through a matrix, I need to use two nested loops like this:

for(int i = 0; i < rows; i++)
    for(int j = 0; j < cols; j++)
        /* code */

I need to be able to save the top left coordinates and the bottom right coordinates of a square in a matrix.

I have the matrix saved in a one-dimensional field as well as the number of rows and cols. This particular matrix would look like this if printed to the screen:

1 0 1 1 1 0 0 1 0 1 0 0 1 1 1

I can't seem to find the right algorithm to recognize a square in any matrix of this kind. Could anyone give me a hint?

Upvotes: 0

Views: 76

Answers (1)

Tim B
Tim B

Reputation: 41168

Simple algorithm:

for(int i = 0; i < rows-2; i++) // scan all but last 2 rows since we scan down once we find the top of a square
    // Reset the count after each row
    int count = 0;
    int lastCell = -1;
    for(int j = 0; j < cols; j++) { // Scan all columns
       // look for 3 cells in a row the same
       if (cells[i][j] == lastCell) {
          count++;
       } else {
          lastCell = cells[i][j];
          count=1;
       }
       if (count >= 3) {
          // Potential match found since we have a row of three the same
          // now check for the sides and bottom
          if (cells[i-2][j+1] == lastCell && cells[i-2][j+2] == lastCell && // left side
              cells[i][j+1] == lastCell && cells[i][j+2] == lastCell && // right side
              cells[i-1][j+2] == lastCell  // bottom
              ) {
                // Square detected - do whatever you like here :)
                // i, j is the top right corner of the detected square
           }
       }
    }

If you need the square to be hollow then check for the center square != lastCell.

If you only need squares of a certain value then only check for that value.

Upvotes: 2

Related Questions