1277. Count Square Submatrices with All Ones

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

Count Square Submatrices with All Ones - LeetCode

행렬에서 정사각형 개수 찾기

 

1. Brute Force

둘레를 따라서 탐색하기 = 대각선으로 탐색하기

오른쪽 아래 방향으로 진행

/**

 * @param {number[][]} matrix

 * @return {number}

 */

var countSquares = function (matrix) {

    let row = matrix[0].length;

    let col = matrix.length;

    let count = 0;

 

    for (let y = 0; y < col; y++) {

        for (let x = 0; x < row; x++) {

            outerLoop: for (let i = 0; y + i < col && x + i < row; i++, count++) {

                for (let j = 0; j <= i; j++) {

                    if (matrix[y + i][x + j] === 0 || matrix[y + j][x + i] === 0) break outerLoop;

                }

            }

        }

    }

    return count;

};

 

2. 개선

특정 위치에서 만들 수 있는 사각형의 개수를 누적하여 기록

 

 

 

 

 

https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/442184/JavaScript-Easy-to-understand-2-solutions