농장의 언덕 지키기
면접 대비시간 제한1초메모리 제한128 MB
8방향으로 인접한 같은 높이의 칸들을 하나의 무리로 묶고, 그 무리가 더 낮은 높이나 지도 경계로만 둘러싸인 개수를 센다.
문제
농장에는 언덕이 여러 개 있고, 농부 John은 소중한 젖소들을 지키기 위해 각 언덕의 꼭대기마다 경비원을 한 명씩 세우려고 한다. 모든 언덕 꼭대기에 경비원을 배치하려면 몇 명이 필요한지, 즉 지도에 언덕 꼭대기가 몇 개나 있는지 구하여라.
지도는 개의 행과 개의 열로 이루어진 정수 행렬로 주어진다 (, ). 행렬의 각 원소는 고도 를 나타내며 이다.
언덕 꼭대기란 값이 모두 같은 하나 이상의 인접한 칸들의 집합으로서, 그 집합의 바깥쪽 경계가 오직 지도의 가장자리이거나 자신보다 고도가 낮은(더 작은) 칸으로만 둘러싸여 있는 것을 말한다. 두 칸이 인접하다는 것은 두 칸의 행 좌표 차이의 절댓값이 이하이고 열 좌표 차이의 절댓값도 이하인 경우를 뜻한다(즉 상하좌우와 대각선을 포함한 8방향).
입력
- 첫째 줄: 공백으로 구분된 두 정수 과 .
- 둘째 줄부터 째 줄까지: 번째 줄에는 행렬의 번째 행이 개의 정수 로 공백으로 구분되어 주어진다.
출력
- 첫째 줄에 언덕 꼭대기의 개수를 하나의 정수로 출력한다.
힌트
예제 입력에서 언덕 꼭대기는 모두 3개이다: 왼쪽 위의 고도 인 칸, 아래쪽에 있는 고도 인 칸들 중 하나, 그리고 오른쪽 위 모서리의 고도 인 칸이다.