c - 在矩阵中查找正方形

Question

我无法想出一种算法来遍历由 0 和 1 组成的矩阵，例如看起来像这样:

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

前两位数字是行数和列数。零是空白，零是实际的“线”。我知道要遍历矩阵，我需要使用两个这样的嵌套循环:

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

我需要能够将正方形的左上角坐标和右下角坐标保存在矩阵中。

我将矩阵以及行数和列数保存在一维字段中。如果打印到屏幕上，这个特定的矩阵看起来像这样:

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

我似乎无法找到正确的算法来识别此类矩阵中的正方形。谁能给我一个提示？

Answer 1

简单算法:

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

如果您需要正方形是空心的，请检查中心正方形 != lastCell。

如果您只需要某个值的平方，则只检查该值。