JOI 칼데라는 경치가 좋아 많은 등산객이 사랑하는 지형이다. 특히 능선이라 부르는 곳에서 보는 경치는 뛰어나다. JOI 칼데라의 땅은 남북으로 \(H\)킬로미터, 동서로 \(W\)킬로미터인 직사각형이다. 남북·동서로 \(1\)킬로미터마다 땅을 나누어 생긴 \(H \times W\)개의 영역을 구역이라 한다. 모든 구역 안에서 고도는 같고, 서로 다른 구역의 고도는 다르다. 어떤 구역에 비가 내리면, 빗물은 그 구역과 동서남북으로 이웃한 최대 \(4\)개 구역 가운데 고도가 더 낮은 모든 구역으로 흐른다. 그런 구역이 없으면 빗물은 그 구역에 고인다. 다른 구역에서 흘러 온 빗물도 같다. JOI 칼데라 바깥은 외륜산의 가파른 절벽으로 둘러싸여 있어, 빗물이 칼데라 밖으로 나가지는 않는다. 어떤 구역에만 비가 내렸을 때 마침내 빗물이 여러 구역에 고이면, 그 구역을 능선이라 한다. 경치를 아끼는 등산객을 위해, 능선인 구역이 몇 개인지 구하라. |
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(M_{1,1}\) \(M_{1,2}\) \(\cdots\) \(M_{1,W}\)
\(M_{2,1}\) \(M_{2,2}\) \(\cdots\) \(M_{2,W}\)
\(\vdots\)
\(M_{H,1}\) \(M_{H,2}\) \(\cdots\) \(M_{H,W}\)
- 입력은 \(1+H\)줄이다.
- 첫째 줄에 정수 \(H\), \(W\)가 공백 하나로 구분되어 주어진다. JOI 칼데라가 남북으로 \(H\)킬로미터, 동서로 \(W\)킬로미터임을 나타낸다.
- 이어지는 \(H\)줄에 각각 정수 \(W\)개가 공백 하나로 구분되어 주어지고, 고도 정보를 나타낸다. \(i\)번째 줄의 \(j\)번째 정수(\(1 \le i \le H\), \(1 \le j \le W\)) \(M_{i,j}\)는 북에서 \(i\)행, 서에서 \(j\)열 구역의 고도이다.
- \((i, j) \ne (k, l)\)이면 \(M_{i,j} \ne M_{k,l}\)이다.
- \(1 \le H \le 1000\)
- \(1 \le W \le 1000\)
- \(1 \le M_{i,j} \le H \times W\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 능선인 구역의 개수를 출력한다.
고도가 \(5, 7, 8, 9\)인 \(4\)개 구역이 능선이다. 예를 들어 고도 \(9\)인 구역에만 비가 내리면 빗물은 마침내 고도 \(1, 2, 3\)인 \(3\)개 구역에 고이므로 능선이다. 고도 \(6\)인 구역에만 비가 내리면 빗물은 고도 \(1\)인 구역에만 고이므로 능선이 아니다.
고도가 \(8, 10, 11, 12\)인 \(4\)개 구역이 능선이다.