최소 비용 연결 칸

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

요약

N과 M이 각각 9 이하인 정수 격자가 주어질 때, 연결된 칸 집합의 총비용 최솟값을 구한다. 공집합도 허용한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

N x M 크기의 직사각형 격자가 1 x 1 칸으로 나누어져 있다. 각 칸에는 정수 하나가 적혀 있으며, 이 값을 그 칸의 비용이라고 한다.

연결된 칸들의 집합 중 비용의 합이 가장 작은 것을 찾아라. 집합의 비용은 포함된 모든 칸에 적힌 비용의 합이다.

칸들의 집합이 연결되어 있다는 것은, 집합 안의 임의의 한 칸에서 다른 칸으로 이동할 때 집합에 포함된 칸들만 지나며 상하좌우로 인접한 칸을 통해 갈 수 있다는 뜻이다. 두 칸은 변을 공유할 때 인접하다. 아무 칸도 고르지 않은 크기 0의 집합도 허용되며, 그 비용은 0이다.

입력

첫째 줄에 자연수 N과 M이 주어진다. N과 M은 9보다 작거나 같다.

둘째 줄부터 N개의 줄에 각 칸의 비용을 나타내는 정수 M개가 주어진다. 각 정수의 절댓값은 1000보다 작거나 같다.

출력

가능한 연결된 칸 집합의 비용 중 최솟값을 출력한다.

예제4

예제 1
입력
```
2 2
-10 1
2 -10
```
예상 출력
```
-19
```
예제 2
입력
```
3 3
1 2 3
4 5 6
7 8 9
```
예상 출력
```
0
```
예제 3
입력
```
2 3
-5 100 -5
-5 100 -5
```
예상 출력
```
-10
```

예제 4

입력

6 5
-1 -1 1 -1 -1
-1 -1 1 -1 -1
-1 -1 1 -1 -1
99 99 99 99 99
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

예상 출력

-11