在矩阵中查找正方形

Question

我很难想出一个算法来通过一个由零和一个矩阵组成的矩阵，例如，看起来像这样：

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！

如果您只需要某个值的正方形，那么只需检查该值。