젖소 스키장

시간 제한1초메모리 제한128 MB

요약

각 칸에서 같거나 낮은 이웃 칸으로 향하는 방향 그래프를 만든 뒤, 전체 그래프를 강하게 연결되게 만드는 데 필요한 양방향 간선의 최소 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, DFS, 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

콜로라도 산속에 사는 농부 Ron은 자신의 젖소들에게 스키를 가르쳤다. 젖소들은 겁이 많아 사람이 붐비는 곳을 싫어하기 때문에, Ron은 농장 뒤편에 자기만의 스키장을 만들기로 했다.

이 스키장은 가로 $W$ 칸, 세로 $L$ 칸인 직사각형 격자이다( $1 \le W \le 500$ , $1 \le L \le 500$ ). 각 칸에는 해발 높이를 나타내는 정수 $H$ 가 있다( $0 \le H \le 9999$ ).

젖소는 변을 맞대고 인접한(상하좌우로 이웃한, 대각선은 불가) 두 칸 사이에서만 스키를 탈 수 있다. 어떤 칸에서 인접한 칸으로 이동하려면 그 칸의 높이가 같거나 더 낮아야 하며, 더 높은 칸으로는 절대 올라갈 수 없다. 높이가 같은 두 인접한 칸 사이에서는 양방향으로 이동할 수 있다.

Ron은 스키와 리프트를 함께 이용하여 젖소가 모든 칸 쌍 사이를 오갈 수 있게 하고 싶다. 리프트는 높이에 상관없이 임의의 두 칸 사이에 놓을 수 있고 양방향이며, 여러 리프트가 서로 교차하거나 같은 칸을 끝점으로 공유해도 된다. 리프트를 놓는 비용이 크므로, Ron은 리프트 수를 최소로 하고 싶다.

젖소가 스키와 리프트를 이용해 임의의 칸에서 다른 임의의 칸으로 이동할 수 있도록 하기 위해 필요한 리프트의 최소 개수를 구하여라.

입력

첫째 줄: 공백으로 구분된 두 정수 $W$ 와 $L$ .
둘째 줄부터 $L+1$ 째 줄까지: 각 줄에 한 행의 칸 높이를 나타내는 $W$ 개의 정수가 공백으로 구분되어 주어진다.

출력

젖소가 스키와 리프트를 함께 이용해 임의의 칸에서 다른 임의의 칸으로 이동할 수 있게 하기 위해 Ron이 지어야 하는 리프트의 최소 개수를 정수 하나로 출력한다.

예제3

예제 1

입력

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

예상 출력

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