시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB78722314832.104%

문제

1*1크기의 정사각형으로 나누어진 N*M크기의 직사각형 종이가 있다. 각 칸에는 정수가 하나씩 쓰여져 있다. 이 숫자를 비용이라고 하자.

이때, 가장 싼 연결된 칸의 집합을 찾는 프로그램을 작성하시오. 연결된 칸의 집합의 비용은 각 칸에 쓰여 있는 비용의 합이다.

칸이 연결되어 있다는 말은 그 집합의 한 칸에서 다른 칸으로 집합에 포함된 인접한 칸을 통해서 모두 이동할 수 있다는 의미이고, 두 칸이 인접해 있다는 소리는, 같은 변을 공유할 때이다. 크기가 0인 집합도 올바른 집합이다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 9보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 숫자가 M개씩 주어진다. 각 숫자는 절댓값이 1000보다 작거나 같은 정수이다.

출력

첫째 줄에 가장 싼 연결된 칸의 집합의 비용을 출력한다.

예제 입력 1

2 2
-10 1
2 -10

예제 출력 1

-19

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

0

예제 입력 3

2 3
-5 100 -5
-5 100 -5

예제 출력 3

-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

예제 출력 4

-11

출처