책 더미

면접 대비

시간 제한1초메모리 제한512 MB

요약

학생이 네 방향에서 바라볼 때, 각 방향의 경계와 타일 사이에 있는 모든 더미보다 높이가 엄격히 큰 타일의 수를 센다.

난이도: 보통10점 중 4점
유형: 배열, 구현, 시뮬레이션, 완전 탐색
정답자: 아직 제출이 없습니다

문제

아글라르곤 마법학교 도서관에 많은 책이 들어왔고, 이 책들을 책장에 정리해야 한다. 도서관 바닥은 같은 크기의 정사각형 타일로 이루어져 있는데, 사서들은 책을 임시로 놓아둘 정사각형 구역(한 변의 길이가 타일 N개)을 표시했다. 책은 표시된 구역 안에서 다른 책 위에 쌓이거나 빈 타일 위에 놓여, 일부 타일에 책 더미가 생겼다. 가장 어린 학생은 모든 책의 정보를 목록에 입력하고 책을 책장에 정리하는 일을 맡았다. 이 소식을 들은 학생은 책 옆에 서서 해야 할 일의 양에 한숨만 쉬었다. 그는 표시된 구역의 가장자리를 따라 걸으며, 구역의 변에 평행한 방향으로 보이는 책 더미의 수를 센다. 어떤 더미는 학생과 그 더미 사이에 더 높은 더미나 같은 높이의 더미가 없으면 보인다. 어린 마법사가 책 옆을 걸으면서 볼 수 있는 더미의 수를 세는 프로그램을 작성하라.

입력

첫째 줄에 표시된 구역의 한 변의 길이 N(1 ≤ N ≤ 50)이 주어진다. 다음 N개 줄에는 각각 공백 하나로 구분된 N개의 음이 아닌 정수가 주어지며, 각 바닥 타일 위 책 더미의 높이(cm)를 나타낸다. 타일에 책이 없으면 더미의 높이는 0이다.

출력

보이는 더미의 수를 출력한다.

힌트

(2, 2) 위치의 더미는 보이지 않으며, (2, 3), (3, 3), (3, 4) 타일에는 책이 없다.

예제1

예제 1
입력
```
4
3 3 2 1
4 1 0 2
3 2 0 0
3 1 2 1
```
예상 출력
```
12
```