JOI 왕국에는 넓은 숲이 있다. 숲은 직사각형이고, 남북으로 \(H\)칸, 동서로 \(W\)칸인 격자로 나뉘어 있다. 북쪽에서 \(i\)칸째, 서쪽에서 \(j\)칸째 (\(1 \le i \le H\), \(1 \le j \le W\)) 구역에는 나무가 \(A_{i,j}\)그루 있다. 다만 북서쪽 끝 구역에는 목재 가공 공장이 있어 나무가 없다. 즉 \(A_{1,1}=0\)이다. 나무가 없는 구역에는 사람이 들어갈 수 있다. 동서남북으로 이웃한 구역에 나무가 없으면 그쪽으로 이동할 수 있다. 숲 밖으로는 나갈 수 없다. JOI 군은 공공사업으로 나무를 베어, 북서쪽 끝 구역과 남동쪽 끝 구역을 서로 오갈 수 있게 하고 싶다. 벌채는 다음과 같이 한다. 처음 JOI 군은 공장이 있는 북서쪽 끝 구역에 있다. 지금 있는 구역과 동서남북으로 이웃하고 나무가 없는 구역으로는 \(1\)분에 이동할 수 있다. 동서남북으로 이웃한, 나무가 있는 구역에서는 \(1\)분에 나무 \(1\)그루를 벨 수 있다. 다만 나무 \(1\)그루를 벨 때마다, 벤 나무를 북서쪽 끝 공장까지 옮겨야 한다. 나무를 옮기는 동안에도 이동 속도는 같다. 나무를 옮기는 동안에는 다른 나무를 벨 수 없다. 조건을 만족하도록 나무를 베는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하라. 여기서 벌채에 걸리는 시간이란, 마지막으로 벤 나무를 공장까지 옮길 때까지의 시간이다. |
입력은 다음 형식으로 주어진다.
\(H\) \(W\)
\(A_{1,1}\) \(\cdots\) \(A_{1,W}\)
\(\vdots\)
\(A_{H,1}\) \(\cdots\) \(A_{H,W}\)
- 첫째 줄에 남북 칸 수 \(H\)와 동서 칸 수 \(W\)가 공백 하나로 구분되어 주어진다.
- 다음 \(H\)줄의 \(i\)번째 줄에 \(W\)개의 정수 \(A_{i,1}, \ldots, A_{i,W}\)가 공백 하나로 구분되어 주어진다.
- \(1 \le H \le 30\)
- \(1 \le W \le 30\)
- \((H, W) \ne (1, 1)\)
- \(0 \le A_{i,j} \le 10000\)
- \(A_{1,1}=0\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 조건을 만족하도록 나무를 베는 데 걸리는 시간의 최솟값을 출력한다.
북쪽에서 \(i\)칸째, 서쪽에서 \(j\)칸째 구역을 \((i, j)\)로 나타낸다. 먼저 \((1, 2)\)의 나무를 베는 데 \(1\)분이 걸린다. 다음 \((1, 3)\)의 나무를 모두 베려면 한 그루당 \(3\)분이 걸려 \(2 \times 3 = 6\)분이 걸린다. 다음 \((2, 3)\)의 나무를 모두 베려면 한 그루당 \(5\)분이 걸려 \(5 \times 5 = 25\)분이 걸린다. 합계 \(1 + 6 + 25 = 32\)분이고, 이보다 짧게 조건을 만족할 수는 없다.
\((2, 5)\)의 나무만 베면 된다.
먼저 \((1, 2)\)의 나무를 베고, 다음에 \((2, 5)\)의 나무를 베면 된다.