LeetCode-1277 统计全为1的正方形子矩阵

📝题目

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的正方形子矩阵的个数。

其中：
· 1 <= arr.length <= 300
· 1 <= arr[0].length <= 300
· 0 <= arr[i][j] <= 1

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7

📝思路

用 f[i][j] 表示以 (i, j) 为右下角的正方形的最大边长，那么除此定义之外，f[i][j] = x 也表示以 (i, j) 为右下角的正方形的数目为 x（即边长为 1, 2, …, x 的正方形各一个）。在计算出所有的 f[i][j] 后将它们进行累加，就可以得到矩阵中正方形的数目。

不难得到 f[i][j] 的递推式：

• if i = 0 or j = 0 : f[i][j] = matrix[i][j];
• if matrix[i][j] = 0 : f[i][j] = 0;
• otherwise : f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1;
  
  
  

📝题解

int countSquares(vector<vector<int>>& matrix) {
    int len1 = matrix.size();
    int len2 = matrix[0].size();
    int f[len1][len2];
    int result = 0;
    for (int i = 0; i < len1; ++i){
        for (int j = 0; j < len2; ++j){
            if (i == 0 || j == 0)
                f[i][j] = matrix[i][j];
            else {
                if (matrix[i][j]){
                    f[i][j] = min(min(f[i][j-1], f[i-1][j]), f[i-1][j-1])+1;
                }
                else    f[i][j] = 0;
            }
            result += f[i][j];
        }
    }
    return result;
}