Informatica Online Judge

  능선 [1834 / 072A]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 8   Total Tried : 15


The Champion of this Problem (C++) : gs17044 - 37ms / 1366byte
My Best Submission (C++) : N/A

[JOI 16/17 예선]

Background

GS 칼데라는 경관이 좋기로 유명하여 많은 등산가들이 찾아온다.

특히 능선은 절경이다.

GS 칼데라의 토지는 세로로 $h$키로미터, 가로로 $w$키로미터의 직사각형의 형태이다.

세로, 가로로 $1$키로미터를 GS칼데라의 한 영역이라고 한다.

모든 영역에대해서 각 영역의 높이는 같다.

또 다른 영역의 높이는 서로 다르다.

어느 영역에 비가 내리면 빗물은 그 영역과 상, 하, 좌, 우로 인접한 최대 4개의 영역들 중 높이가 그 영역보다 낮은 영역으로 흘러간다.

다른 영역으로부터 흘러온 빗물은 같은 방법으로 계속 흘러간다.

GS칼데라의 외부는 매우 높은 산으로 둘러쌓여 있어서 GS칼데로 외부로 빗물이 흘러가지는 않는다.

어느 영역에 대해서 그 영역에 비가 내린 후, 이 빗물이 더 이상 흘러가지 않고 고이게 된다.

만약 임의의 한 영역에 비가 온다고 하자.

이 빗물은 이 영역으로부터 출발하여 어딘가에 고이게 될 것이다.

어떤 영역으로부터 출발했을 때, 마지막으로 고이는 영역의 수가 2개 이상이 되는 출발영역을 능선이라고 한다.

절경을 너무나도 좋아하는 경곽이는 이러한 능선이 몇개나 되는지 궁금해졌다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 2개의 정수 $h$, $w$가 공백으로 구분되어 입력된다.

두 번째 줄부터 $h$줄에 걸쳐서 각 줄에 $w$개 씩 각 영역의 높이가 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1 ≦ h ≦ 1000, 1 ≦ w ≦ 1000, 1 ≦ 각 영역의 높이 ≦ h*w$

Output

능선의 수를 출력한다.

IO Example

입력
3 3
2 9 4
7 5 3
6 1 8

출력
4

입력2
3 5
5 3 8 2 14
9 10 4 1 13
12 7 11 6 15

출력2
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]