JOI 2017 예선 5- 능선 > 문제은행 : 정보올림피아드&알고리즘




3032 : 능선

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
8 회   
시도횟수
34 회   

문제

KOI 산에는 아주 유명한 골짜기가 있다. 이 골짜기는 H m × W m 크기이며, H×W개의 주상절리가 격자 형태로 놓여있다. 위에서 a번째, 왼쪽에서 b번째에 있는 주상절리는 고도가 H[a][b]이다. 골짜기 주변에는 커다란 절벽이 둘러싸여 있다.

 

KOI 산의 골짜기에는 몇 개의 사진 명소가 있다. 능선에서 사진을 찍으면 매우 아름다운 절경이 나오는데, 능선은 아래 조건을 만족해야 한다.

 

▷ 능선에서 비가 살짝 내려서 상하좌우 네 방향으로 빗물이 흐를 때, 물이 고이는 지점이 2개 이상 생겨야 한다.

 

당신은 KOI 산의 관광 가이드로서 골짜기에 얼마나 많은 능선이 있는지 찾아야 한다. 골짜기의 고도 정보가 주어졌을 때 능선의 수를 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 골짜기의 크기 H, W가 주어진다. (1 ≦ H, W ≦ 1,000) 두 번째 줄부터 H개의 줄에는 골짜기의 정보가 주어진다. 1+a번째 줄의 b번째 수는 위에서 a번째, 왼쪽에서 b번째 지역의 고도 H[a][b]가 주어진다. H[a][b]는 1 이상 H × W 이하이며 모두 다르다.

출력형식

첫 번째 줄에 능선의 수를 출력한다. 전체 데이터의 20%는 H, W ≦ 50을 만족한다.

입력 예

3 3
2 9 4
7 5 3
6 1 8

출력 예

4

입력 예

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

출력 예

4

Hint!

예제 1의 경우 고도가 5, 7, 8, 9인 지역이 능선이다. 고도가 6인 지역의 경우 비가 내리면 고도가 1인 지역에만 물이 고이기 때문에 능선이 아니다. 예제 2의 경우 고도가 8, 10, 11, 12인 지역이 능선이다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP