统计全为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[i][j] <= 1
通过次数12,484提交次数17,559

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力求解

class Solution {
    public int countSquares(int[][] matrix) {

        int h = matrix.length;
        int w = matrix[0].length;

        int max = Math.min(h, w);
        int count = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                for (int i = 1; i <= max; i++) {
                    boolean flag = isSqare(matrix, y, x, y + i, x + i, h, w);
                    if (flag) {
                        // System.out.println(y + "\t" + x + "\t" + i);
                        count++;
                    }
                }
            }

        }
        return count;

    }

    //判断矩形里面是不是全是1
    public boolean isSqare(int[][] matrix, int y1, int x1, int y2, int x2, int h, int w) {
        if (y2 > h || x2 > w) {
            return false;
        } else {
            for (int i = y1; i < y2; i++) {
                for (int j = x1; j < x2; j++) {
                    if (matrix[i][j] == 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

赏

谢谢你请我吃糖果

微信