Informatica Online Judge

  금강산 [2008 / 07D8]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 84   Total Tried : 164


The Champion of this Problem (C++) : gs16004 - ms / 467byte
My Best Submission (C++) : N/A

[USACO 2008/11]

Background

지용이는 금강산에 정말 일만이천봉이 있는지 호기심이 든 나머지 북한의 정보통신망을 해킹해서 금강산의 지도를 빼돌렸다.

애석하게도 북한의 기술력은 생각보다 좋지 않아서 지도는 $N × M$ 크기의 저해상도지만, 그래도 산봉우리의 개수를 세기에 충분하다고 생각한 지용이는, 다음과 같은 것을 산봉우리라고 정의했다.

* 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. 상하좌우 및 대각선으로 붙어있는 격자를 인접하다라고 한다.

* 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

지용이를 도와 지도 안의 산봉우리의 개수를 세어주자.

Input

첫번째 줄에 $N$, $M$이 주어진다.

이후 $N$개의 줄에 $M$개의 정수가 주어진다.

[입력값의 정의역]

$1 ≤ N, M ≤ 100$
입력되는 각 높이 값은 $10,000$ 이하의 자연수

Output

산봉우리의 개수를 출력한다.

IO Example

입력
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

출력
3

* 설명 : ($1$, $1$)의 높이 $4$인 봉우리 와, ($1$, $7$) ($2$, $7$)로 이루어진 높이 $1$의 봉우리, 마지막으로 ($7$, $3$), ($7$, $4$), ($8$, $5$)로 이루어진 높이 $2$인 봉우리로 모두 $3$개이다.

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