1277. Count Square Submatrices with All Ones
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
Count Square Submatrices with All Ones - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
행렬에서 정사각형 개수 찾기
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. 개선
특정 위치에서 만들 수 있는 사각형의 개수를 누적하여 기록