1로 구성된 submatrix란 위 그림에서 빨간색으로 표시해놓은 1로 구성된 행렬을 의미한다.
submatrix의 합을 구하는 방법은 아래 코드와 같다
var countSquares = function(matrix) {
let row = matrix.length;
let column = matrix[0].length;
for(let i=1;i<row;i++) {//(*)
for(let j=1;j<column;j++) {
if(matrix[i][j] && matrix[i-1][j] && matrix[i][j-1] && matrix[i-1][j - 1]) {
matrix[i][j] = Math.min(matrix[i-1][j - 1], matrix[i][j-1], matrix[i-1][j]) + 1;
}
}
}
let sum = 0;
for(let i=0;i<row;i++) {
sum += matrix[i].reduce((a,b) => a + b, 0);
}
return sum;
};
(*)표시된 반복문이 핵심이니 이부분만 설명한다.
[1,1]부터 시작해서 [1,1]'(현재위치), [0,1]'(위), [1,0]'(왼쪽), [0,0]'(왼쪽위)이 모두 0이 아니면 [0,1], [1,0], [0,0]의 최소값+1을 반환한다.