Python 中查詢具有 1 的正方形子矩陣數量的程式

假設我們有一個 2D 二進位制矩陣，我們需要找到其中等於 1 的正方形子矩陣的總數量。

所以，如果輸入如下

那麼輸出將是 17，因為有 12 個 (1 x 1) 正方形、4 個 (2 x 2) 正方形和 1 個 (3 x 3) 正方形。

為了解決這個問題，我們將遵循以下步驟 −

• res := 0
• 對於 0 到矩陣行數範圍內的 i，執行
  • 對於 0 到矩陣列數範圍內的 j，執行
    • 如果 i 等於 0 或 j 等於 0，那麼
      • res := res + matrix[i, j]
    • 否則，當 matrix[i, j] 等於 1 時，那麼
      • matrix[i, j] = minimum of (matrix[i, j - 1], matrix[i - 1, j] and matrix[i - 1, j - 1]) + 1
      • res := res + matrix[i, j]
• 返回 res

我們來看一下以下實現以獲得更好的理解 −

示例 

線上演示

class Solution:
   def solve(self, matrix):
      res = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if i == 0 or j == 0:
               res += matrix[i][j]
            elif matrix[i][j] == 1:
               matrix[i][j] = min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1
               res += matrix[i][j]
      return res

ob = Solution()
matrix = [
   [1, 1, 1, 0],
   [1, 1, 1, 0],
   [1, 1, 1, 0],
   [0, 0, 0, 0],
   [1, 0, 1, 1]
]
print(ob.solve(matrix))

輸入

matrix = [  
[1, 1, 1, 0],  
[1, 1, 1, 0],  
[1, 1, 1, 0],  
[0, 0, 0, 0],  
[1, 0, 1, 1]
]

輸出

17

Arnab Chakraborty

更新於： 02-12-2020

96 次瀏覽

開啟你的職業生涯

透過完成課程來獲得認證

開始