파이프

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

요약

각 모듈 사이 벽에 비용이 주어진 격자에서 서비스 모듈에서 시작해 모든 모듈을 한 번씩 지나 다시 돌아오는 최소 비용 순환 경로를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 행렬, 그리디
정답자: 아직 제출이 없습니다

문제

사무용 건물을 짓는 일은 매우 표준화되었다. 미리 제작된 모듈을 고객의 요구에 맞게 조합하고, 멀리 떨어진 공장에서 실어 와 현장에서 조립한다. 그래도 여전히 세심한 계획이 필요한 작업이 있는데, 그중 하나가 난방 배관을 어떻게 놓을지 정하는 일이다.

현대식 사무용 건물은 정사각형 모듈들로 이루어진다. 각 층에는 서비스 모듈이 정확히 하나 있으며, 이 모듈에서 (여러 가지 중에서도) 난방 배관을 통해 나머지 모듈들로 온수를 내보낸다. 서비스 모듈을 포함한 모든 모듈은 이웃한 두 개에서 네 개의 모듈 중 정확히 두 개와 난방 배관으로 연결된다. 따라서 배관은 서비스 모듈에서 출발하여 모든 모듈을 정확히 한 번씩 지난 뒤 다시 서비스 모듈로 돌아오는 하나의 폐회로를 이룬다.

모듈마다 성질이 달라, 인접한 두 모듈을 연결하는 비용도 서로 다르다. 예를 들어 두 모듈 사이에 두꺼운 벽이 있으면 배관을 놓는 비용이 커진다. 한 층의 정보가 주어질 때, 난방 배관을 놓는 가장 저렴한 방법을 구하라.

입력

첫 줄에는 처리할 층의 수를 나타내는 정수 하나가 주어진다. 이어서 그 수만큼의 층 정보가 주어진다.

각 층 정보는 새 줄에서 두 정수 $2 \le r \le 10$ 과 $2 \le c \le 10$ 으로 시작하며, 층의 크기는 $r$ 행 $c$ 열의 모듈이다. 다음 $2r + 1$ 개의 줄에 층이 ASCII로 그려지며, 각 줄은 $2c + 1$ 개의 문자로 이루어진다.

이 그림에서 바깥 경계는 # 로 그려지고, 각 모듈의 중심은 공백이다. 인접한 두 모듈을 나누는 내부 벽은 하나의 숫자 0–9 로, 그 벽을 통해 배관을 놓는 비용을 뜻한다. 모든 층은 완전한 직사각형이며 모듈 수는 항상 짝수이다.

출력

각 층마다 가장 저렴한 경로의 비용을 한 줄에 출력한다.

예제4

예제 1

입력

3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####

예상 출력

28
45
10

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

예제 3

입력

1
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######

예상 출력

예제 4
입력
```
1
2 2
#####
# 0 #
#5#0#
# 9 #
#####
```
예상 출력
```
14
```