本文主要是介绍Lintcode 1869 · Count Square Submatrices with All Ones [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用DP来做，dp使用2纬的表示以i，j为右下角的全1方阵一共多少个。以一个22的0/1矩阵来看，可以看到，如果右下角是0，则以其为右下角的方阵数量为0，在看其周围的三个元素，只要有一个为0，则以右下角为方针的数量只有0.以此类推到33的矩阵，可以知道，状态转移为dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1, 当然了，前提是matrix[i+1][j+1]是1.
class Solution:"""@param matrix: a matrix@return: return how many square submatrices have all ones"""def countSquares(self, matrix):# write your code heredp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]res = 0for i in range(len(matrix)):for j in range(len(matrix[0])):if i == 0 or j == 0:dp[i][j] = matrix[i][j]elif matrix[i][j] == 0:dp[i][j] = 0else:dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1res += dp[i][j]return res
1869 · Count Square Submatrices with All Ones
Algorithms
Medium
Accepted Rate
68%
DescriptionSolutionNotesDiscussLeaderboard
Description
Given a m * n matrix of ones and zeros, please count and return the number of square submatrix completely composed of 1.
1 <= arr.length <= 300
1 <= arr[0].length <= 300
Example
Example 1:
Input:
matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output:
15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output:
7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
这篇关于Lintcode 1869 · Count Square Submatrices with All Ones [Python]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
