在Python中统计给定二进制矩阵中正方形子矩阵的数量
假设我们有一个二维二进制矩阵。我们必须查找矩阵中出现的所有元素都为1的正方形子矩阵的总数。
因此,如果输入是这样的:
0 | 1 | 1 |
---|---|---|
0 | 1 | 1 |
那么输出将为5,因为有一个(2 x 2)正方形和四个(1 x 1)正方形。
为了解决这个问题,我们将遵循以下步骤-
- 如果mat为空,则
- 返回0
- c := 0
- 对于i在mat的行数上从0到循环,执行以下操作 –
- 对于j在mat的列数上从0到循环,执行以下操作-
- 如果mat[i, j]是1,则
- 如果i为0或j为0,则
- c := c + 1
- 否则,
- temp =(min(mat[i-1,j-1],mat[i,j-1]和mat[i-1,j])+ mat[i,j]
- c := c + temp
- mat[i,j] := temp
- 对于j在mat的列数上从0到循环,执行以下操作-
- 返回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]]
输出
5