【数据布局-二维前缀和】力扣1277. 统计全为 1 的正方形子矩阵 ...

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出：15
解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
提示：
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[j] <= 1

1. class Solution {
2. public:
3.     int countSquares(vector<vector<int>>& matrix) {
4.         int m = matrix.size(), n = matrix[0].size();
5.         int ans = 0;
6.         vector<vector<int>> dp(m, vector<int>(n));
7.         for(int i = 0; i < m; i++){
8.             for(int j = 0; j < n; j++){
9.                 if(i==0 || j==0){
10.                     dp[i][j] = matrix[i][j];
11.                 }
12.                 else if(matrix[i][j] == 0){
13.                     dp[i][j] = 0;
14.                 }
15.                 else{
16.                     dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
17.                 }
18.                 ans += dp[i][j];
19.             }
20.         }
21.         return ans;
22.     }
23. };

复制代码

该题和力扣221.最大正方形类似，以某一格为右下角能形成最大正方形的边长，就是以该格为右下角的正方形数量。详情主页找力扣221

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。