Elevator Pitch

면접 대비

시간 제한2초메모리 제한512 MB

요약

각 칸에 층수가 주어진 격자에서, 같은 층의 인접 이동과 수직 이동을 이용해 모든 건물의 모든 층에 도달하도록 필요한 최소 엘리베이터 수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, BFS, 구현
정답자: 아직 제출이 없습니다

문제

You are in charge of ensuring all building designs meet accessibility requirements. As law dictates, every part of your building should be reachable for wheelchair users, which means elevators will have to be installed. You are given the blueprints of the company's current project and have to determine the minimum number of elevators required.

The floor plan is laid out on a square grid and the blueprints tell you the number of floors above any given square. You can place an elevator at any square, which stops at all floors of that square. A wheelchair user can move up and down between floors using the elevators and can freely move to any of the four adjacent squares on the same floor. Buildings do not connect diagonally.

The image below shows the second sample input. Designs can consist of multiple buildings; this one contains three buildings. The design requires two elevators: one for the pyramid-shaped building and one for the tall tower. The small building of height one does not require an elevator, since it only has a ground floor.

Figure E.1: A visualisation of the second sample input.

입력

One line containing integers $h$ and $w$ ( $1\leq h, w\leq 500$ ), the height and width of the grid.
$h$ lines of $w$ integers each, where $x\_{i,j}$ ( $0\leq x\_{i,j} \leq 10^9$ ), the $j$ th integer on the $i$ th line, denotes the number of floors at position $(i,j)$ of the grid.

출력

Output the minimum number of elevators you need to build to be able to reach every part of the building(s) in the grid.

예제3

예제 1
입력
```
3 3
1 2 3
0 0 4
7 6 5
```
예상 출력
```
1
```

예제 2

입력

6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0

예상 출력

예제 3
입력
```
4 4
1 1 2 1
2 2 1 2
1 2 2 1
2 1 2 2
```
예상 출력
```
4
```