LeetCode-1277. Count Square Submatrices with All Ones

LeetCode-1277. Count Square Submatrices with All Ones

Given a ​​m * n​​ matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =[ [0,1,1,1], [1,1,1,1], [0,1,1,1]]Output: 15Explanation: 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: 7Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

Constraints:

​​1 <= arr.length <= 300​​​​1 <= arr[0].length <= 300​​​​0 <= arr[i][j] <= 1​​

题解：

class Solution {public: int countSquares(vector>& matrix) { if (matrix.empty() == true) { return 0; } int m = matrix.size(), n = matrix[0].size(); int res = 0; vector> dp(m + 1, vector(n + 1, 0)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { dp[i + 1][j + 1] = 1 + min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}); res += dp[i + 1][j + 1]; } } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。