1277. Count Square Submatrices with All Ones

문제

풀이

matrix =
[1,1],
[1,1]
일 때 직관적으로 나타낼 수 있다.
[1,1],
[1,2]
side 1 => 4
side 2 => 1 이기 때문이다.

matrix =
[1,1,1],
[1,1,1],
[1,1,1]
일 때 직관적으로 나타낼 수 있다.
[1,1,1],
[1,2,2],
[1,2,3],
side 1 => 9
side 2 => 4
side 3 => 1이기 때문이다.

matrix =
[1,1],
[0,1],
일 때 직관적으로 나타낼 수 있다.
[1,1],
[0,1]
side 1 => 3이기 때문이다. 그 이유는 '0'이 있어 정사각형이 더 이상 만들어지지 않기 때문이다.

Example 1을 기준으로 위에 로직처럼 나타낸다면 다음과 같다.

1. 만약 left, top, side, me중에서 0이 포함되어 있으면 정사각형이 만들어지지 않기 때문에 현재값을 캐시에 저장한다.
2. 만약 left, top, side 모두 같고 1이상이라면 길이가 증가된 정사각형을 만들 수 있으므로 left + 1 해준다.
3. 만약 left, top, side 중 1이상이지만 서로 다른값이 있으면 최소값 + 1을 해준다.

결과