그리드 그래프의 최소 비용 신장 트리

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

요약

정수 격자가 주어지고 같은 행이나 열에 있는 두 칸을 절댓값 차를 가중치로 연결할 때, 이 그래프의 최소 신장 트리 비용을 구한다.

문제

$n \times m$ 크기의 정수 그리드가 주어진다.

다음과 같은 그래프를 생각하자. 그리드의 각 칸을 정점으로 본다. 같은 행이나 같은 열에 있는 두 칸 사이에는 간선이 있으며, 간선의 비용은 두 끝점에 적힌 수의 절댓값 차이다.

이 그래프의 최소 비용 신장 트리(신장 트리의 비용은 포함된 간선 비용의 합)의 비용을 구하라.

첫째 줄에 그리드의 행 개수와 열 개수 $n$ , $m$ 이 주어진다. ( $1 \leq n \cdot m \leq 10^5$ )

이어서 $n$ 개의 줄이 주어진다. $i$ 번째 줄에는 그리드의 원소 $a_{i,j}$ 가 $m$ 개 주어진다. ( $0 \leq a_{i,j} < 10^9$ )

최소 비용 신장 트리의 비용을 정수 하나로 출력한다.