암벽등반 - 구름LEVEL
암벽등반
Quiz Info
Quiz Info
암벽등반
100points
Participant
2
Solved Rate
50%
2
0

구름이는 암벽등반에 도전하려고 합니다. 등반할 장소는 각 장소의 돌출 정도가 표시되어 있고, 많이 튀어나와 있을수록 그 값이 큽니다.

구름이의 체력은 HP로 표현되며, 체력이 HP라면 현재 위치에서 HP값 이하의 상, 하, 좌, 우 장소로만 이동할 수 있습니다.

구름이가 이번에 참가할 암벽등반 대회의 코스 정보가 지도로 주어지는데, 이 지도는 N × N으로 구성된 정사각형의 형태입니다.

구름이는 임의의 장소에서 출발할 수 있고, 끝나는 장소도 임의의 장소에서 끝낼 수 있습니다

등반 성공 여부는 주어진 지도에 표시된 코스의 3/4 이상의 위치를 지나가야 성공으로 판정됩니다.

구름이가 주어진 지도의 암벽등반을 무사히 완주하기 위해서 필요한 최소 체력(HP)를 구하는 프로그램을 작성하세요.


* 3/4가 실수일 경우에는 소수점 이하를 버린 값만큼만 등반하면 성공. 만약 N이 7 이라면 모두 49개의 등반 장소가 있고, 3/4는 36(36.75)이므로 36개의 등반 장소를 거쳤을 경우 성공


입력

첫 번째 줄에 등반 코스의 크기 N ( 500 이하 자연수 )

각 장소의 돌출 정도(영역별 높이)가 N 줄에 걸쳐 공백으로 구분되어 입력

출력

등반에 필요한 최소 체력(HP)



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
5
55550
00050
33255
00335
30302
Output
3
Example 2
Input
5
99933
00003
09933
00033
90093
Output
3
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)