# 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: 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.
``````

Constraints:

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

``````class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), res = 0;
vector<vector<int>> sums(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sums[i][j] = matrix[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 0; i + k <= m && j + k <= n; ++k) {
if (sums[i + k][j + k] - sums[i - 1][j + k] - sums[i + k][j - 1] + sums[i - 1][j - 1] == (k + 1) * (k + 1)) {
++res;
}
}
}
}
return res;
}
};
``````

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1277

Minimum Cost Homecoming of a Robot in a Grid

Count Fertile Pyramids in a Land

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441306/JavaC%2B%2BPython-DP-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation