바둑판처럼 점들의 2차 배열로 구성되어 있는 판에 일부의 점들은 선으로 연결되어 있고 나머지 점들은 연결되어 있지 않다.

이때 특정 크기의 정사각형 개수가 몇 개인지 알아보려고 한다.

예를 들어 아래 그림은 크기 1인 정사각형 2개와 크기 2인 정사각형 1개로 구성되어 있다.

(여기에서 크기는 정사각형 한 변을 구성하는 선의 개수이다.)

이제 주어진 판에서 모든 가능한 정사각형의 개수를 세는 과정을 수행하는 프로그램을 작성하시오.

각 판은 n(2≤n≤20)개의 점들의 2차 배열과 수평선, 수직선으로 구성되어 있다.

H(i, j)는 판 위의 점 (i, j) 와 (i, j+1)을 연결하는 수평선이 존재하는 가를 나타내며,

V(i, j)는 점(i, j) 와 (i+1, j)를 연결하는 수직선이 존재하는 가를 나타낸다.

연결선이 존재하면 1, 존재하지 않으면 0의 값을 갖는다.

위의 판은 이차원 배열 H(n, n), V(n, n)을 이용하여 판 위의 연결된 수평 수직선의 존재를 표현하면 다음과 같다.

정사각형 수 timer 1s memory 128MB

정사각형 수 1s 128MB