在矩陣中查找正方形

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！

如果您只需要某個值的正方形，那麼只需檢查該值。