20644: 统计全为 1 的正方形子矩阵

http://cs101.openjudge.cn/practice/20644/

给一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，

请你统计并输出其中完全由 1 组成的正方形子矩阵的个数。

备注:请尽量用动态规划

输入

第一行是m n 两个数字，空格分开 m行，每行有n个数

输出

一个非负整数

样例输入

样例输出

提示

边为1的矩阵有10个边为2的矩阵有4个边为3的矩阵有1个总共15个

python

#23n2300017735(夏天明BrightSummer)
m, n = map(int, input().split())
mat = [[int(k) for k in input()] for i in range(m)]
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m):
    for j in range(n):
        if mat[i][j]:
            dp[i+1][j+1] = min(dp[i][j], dp[i][j+1], dp[i+1][j])+1
print(sum(dp[i][j] for j in range(n+1) for i in range(m+1)))

Brute force

python

m,n = map(int, input().split())
matrix = []
for i in range(m):
    matrix.append(list(map(int, list(input()))))

def check(matrix, i, j, step):
    for x in range(i, i+step+1):
        for y in range(j, j+step+1):
            if matrix[x][y] == 0:
                return False
    return True

cnt = 0
step = 0

while step <= min(m, n):
    for i in range(m-step):
        for j in range(n-step):
            if check(matrix, i, j, step):
                cnt += 1
    step += 1

print(cnt)

20644: 统计全为 1 的正方形子矩阵 ​

20644: 统计全为 1 的正方形子矩阵