2024 10 27 1277. Count Square Submatrices with All Ones

문제

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

요약

1만으로 체워진 사각형 갯수 찾기

풀이

누적합으로 풀면 쉬울것 같았다.

행으로 누적합을 구한 매트릭스에서 다시 열로 다 더해서 누적합을 2*2 매트릭스를 만들면

정사각형의 변 길이를 s라고 하였을때 [r][c],[r-s+1][c],[r][c-s+1],[r-s+1][c-s+1]이 만드는 사각형 내부의 값의 총 합은

sum = prefix[r][c] - prefix[r-s][c] -prefix[r][c] + prefix[r-s][c-s]

가 된다.

코드

class Solution {
    public int countSquares(int[][] matrix) {
        int maxSize = Math.min(matrix.length, matrix[0].length);
        int[][] prefix = new int[matrix.length][matrix[0].length];
        prefixSum(matrix, prefix);
        int result = 0;
        for (int size = 1; size <= maxSize; size ++) {
            result += window(size, prefix);
        }
        return result;
    }

    private void prefixSum(int[][] matrix, int[][] prefix) {
        for (int r = 0; r < matrix.length; r ++) {
            int[] rowPrefix = new int[matrix[0].length];
            for (int c = 0; c < matrix[0].length; c ++) {
                rowPrefix[c] += c != 0 ? rowPrefix[c -1] + matrix[r][c] : matrix[r][c];
                prefix[r][c] = r != 0 ? prefix[r-1][c] + rowPrefix[c] : rowPrefix[c];
                System.out.print(prefix[r][c] + " ");
            }
            System.out.println();
        }
    }

    private int window(int size, int[][] prefix) {
        int count = 0;
        int max = size * size;
        for (int r = size - 1; r < prefix.length; r ++) {
            for (int c = size - 1; c < prefix[0].length ; c ++) {
                int over = r - size >= 0 ? prefix[r-size][c] : 0;
                int leftOver = r - size >=0 && c - size >=0 ? prefix[r-size][c-size] : 0;
                int left = c - size >= 0 ? prefix[r][c-size] : 0;
                int total = prefix[r][c];
                int sum = total - over - left;

                if (prefix[r][c] - over - left + leftOver == max) {
                    count ++;
                }
            }
        }
        return count;
    }
}

풀이 시간

20분

체감 난이도

easy ~ 중간