Python程式：統計給定二進位制矩陣中正方形子矩陣的數量

假設我們有一個二維二進位制矩陣。我們必須找到矩陣中所有元素都為1的正方形子矩陣的總數。

所以，如果輸入如下：

0	1	1
0	1	1

那麼輸出將是5，因為有一個(2 × 2)的正方形和四個(1 × 1)的正方形。

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

如果mat為空，則
- 返回0
c := 0
對於i從0到mat的行數，執行：
- 對於j從0到mat的列數，執行：
  - 如果mat[i, j]為1，則
    - 如果i為0或j為0，則
      - c := c + 1
    - 否則，
      - temp = (mat[i-1, j-1]，mat[i, j-1]和mat[i-1, j]中的最小值) + mat[i, j]
      - c := c + temp
      - mat[i, j] := temp
返回c

示例

讓我們看看下面的實現，以便更好地理解：

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

輸入

[[2, 6],[3, 4],[4, 7],[5, 5]]

輸出

Arnab Chakraborty

更新於：2021年10月18日

392 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始