COCI 2014/2015 contest2 5- 마법의 숲(SUMA) > 문제은행 : 정보올림피아드&알고리즘




2889 : 마법의 숲(SUMA)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
14 회   

문제

택완이는 마법의 숲에 산다. 숲에 있는 나무들은 매우 키가 크고 빨리 자란다.
숲은 N*N개의 필드로 구성된 행렬 모양이며 하나의 필드에는 하나의 나무가 자란다.
택완이는 이 숲을 매우 좋아하며 특히 나무들이 자라는 것을 관찰하고 키를 측정하는 즐긴다.
나무들은 일정한 비율로 성장한다. 예를 들어 일년에 5m를 자라는 나무라면 6개월에 2.5m를 자란다.

 

어느날 문득 택완이는 나무의 높이가 같아지는 연결된 가장 많은 필드의 개수가 궁금해졌다.

 

여기서 잠깐 용어를 정리하면
두 개의 나무가 인접하다는 것은 어느 하나의 나무에서 볼 때 다른 하나의 나무가 상하좌우 중 한 곳에 위치한 것을 의미한다.
연결되었다는 것은 연속하여 인접한 경우를 말한다. A나무가 B나무와 인접하고 B나무가 C나무와 인접할 경우 A, B, C는 모두 서로 연결되었다고 한다.

 

아래 예를 보자.
(1)번 그림은 택완이가 측정할 당시 숲의 모양이고 각 필드에 사는 나무의 키를 나타낸다.
(2)번 그림은 각 필드에 사는 나무들이 1년에 성장하는 높이이다.
(3)번 그림은 나무의 높이가 같아지는 연결된 필드의 개수가 가장 많을 때로 1년 후 7개 이다.

 

 


입력형식

첫 행에 필드 한 변의 길이 N ( 1 ≤ N ≤ 700)이 주어진다. 다음 N행 N열에 걸쳐 택완이가 측정한 숲의 나무의 키 Hij ( 1 ≤ Hij ≤ 106)가 주어진다. 다음 N행 N열에 걸쳐 각 필드의 나무가 일 년에 성장하는 높이 Vij ( 1 ≤ Vij ≤ 106)가 주어진다.

출력형식

택완이가 궁금해하는 문제의 답을 하나의 행에 출력한다.

입력 예

3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

출력 예

7

입력 예

2
3 1
3 3
2 5
2 5

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP