문제
정올이는 아삭한 당근을 먹으며, 토끼답게 당근의 맛에 대해 생각하고 있었습니다. 그는 농장의 기초 수준인 평지에서 자라는 당근만 즐겨 먹고, 그보다 1미터 높은 고도의 당근은 더 질기고 맛이 없다는 것을 알게 되었습니다. 고도가 높아질수록 나쁜 당근은 점점 더 나빠졌습니다.
정올이는 당근을 씹으면서, 그는 이 맛없는 당근이 언덕의 측면에 자생하여 연하고 맛있는 당근의 바다 사이에 나쁜 당근의 '섬'을 형성한다는 것을 깨달았습니다.(당연히 맛없는 당근은 나쁜 당근이다)
정올이는 실험복을 입고 자신의 목초지에 나쁜 당근의 섬이 몇 개인지 알아내기로 결심했습니다. 그는 목초지를
그는 섬을 세기 시작했습니다. 두 정사각형이 수평, 수직 또는 대각선 방향으로 이웃한다면, 그들은 같은 섬의 일부로 간주됩니다.
그는 제공된 각 지도에서 나쁜 당근의 섬이 몇 개인지 세었습니다.
입력
첫 줄에 두 정수
두 번째 줄부터
[제약 조건]
1 < R,C \le 1,000 1 \le A_{i,j} \le 2,000
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 50점 | |
| #2 | 50점 | 추가 제약 조건 없음 |
예제1
입력
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
출력
2
태그
출처
USACO December 2008 Bronze 2번