정사각형 수 > 문제은행



문제은행

1838 : 정사각형 수

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 3 회    시도횟수: 7 회   



바둑판처럼 점들의 2차 배열로 구성되어 있는 판에 일부의 점들은 선으로 연결되어 있고 나머지 점들은 연결되어 있지 않다. 이때 특정 크기의 정사각형 개수가 몇 개인지 알아보려고 한다. 예를 들어 아래 그림은 크기 1인 정사각형 2개와 크기 2인 정사각형 1개로 구성되어 있다.(여기에서 크기는 정사각형 한 변을 구성하는 선의 개수이다.)

 

 

07f1ee470c4ca420b78cf86b19196679_1450339 

 

이제 주어진 판에서 모든 가능한 정사각형의 개수를 세는 과정을 수행하는 프로그램을 작성하시오. 각 판은 n(2≤n≤20)개의 점들의 2차 배열과 수평선, 수직선으로 구성되어 있다. H(i, j)는 판 위의 점 (i, j) 와 (i, j+1)을 연결하는 수평선이 존재하는 가를 나타내며, V(i, j)는 점(i, j) 와 (i+1, j)를 연결하는 수직선이 존재하는 가를 나타낸다. 연결선이 존재하면 1, 존재하지 않으면 0의 값을 갖는다.

 

 

07f1ee470c4ca420b78cf86b19196679_1450339 

 

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

 

07f1ee470c4ca420b78cf86b19196679_1450339 

 




첫 번째 줄에는 판의 크기인 n이 주어진다.
두 번째 줄부터 수평선에 대한 값 (n-1×n) 행렬이 주어진다.
다음 줄 부터는 수직선에 대한 값 (n×n-1) 행렬이 주어진다.




각 자료에 대해 사각형이 존재하는 크기순으로 한 줄에 하나의 사각형씩 각각의 개수를 출력하시오.



4
1 0 1
1 1 1
0 1 0
0 1 1
1 1 0 1
0 1 1 1
0 1 0 1
2 1
1 2






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.