Informatica Online Judge

  벌목하기 [2153 / 0869]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : gs17003 - 0ms / 1123byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

GSHS나라에는 거대한 삼림이 있다.

이 삼림은 직사각형으로 구성되어 있으며 $H$행, $W$열로 구성되어있다.

위로부터 $i$번째 칸, 왼쪽으로부터 $j$번째 칸의 영역에는 $A_{i,j}$그루의 나무가 자라고 있다.

단, 1행 1열에는 목재가공소가 위치하고 있으며 여기에는 나무가 자라지 않는다. 즉 $A_{1,1} = 0$이다.

나무가 자라지 않는 영역에는 사람이 들어갈 수 있다. 또 사람은 상, 하, 좌, 우 중 나무가 없는 인접한 영역으로 이동할 수 있지만 삼림 외부로는 나갈 수 없다.

경곽이는 GSHS왕국의 나무를 베어서 $(1, 1)$로부터 $(H, W)$까지를 왕복할 수 있도록 하고자 한다.

나무를 베기위해서는 다음과 같은 과정이 필요하다.

처음에 곽이는 목재가공소가 있는 $(1, 1)$에 있다. 경곽이는 현재 있는 영역과 상, 하, 좌, 우로 인접한 나무가 없는 영역으로 1분 동안에 이동할 수 있다.

또 상, 하, 좌, 우로 인접한 영역에 나무가 있다면 1분 동안 1그루의 나무를 벨 수 있다.

단 나무를 1그루 베면 그 때마다 $(1, 1)$에 있는 목재가공소까지 운반하지 않으면 안된다.

나무를 운반하는 동안에도 경곽이는 이동속도는 일정하며 무를 운반하는 동안 다른 나무를 벨 수는 없다.

조건을 만족하도록 나무를 베는데 걸리는 시간을 최소화하고 싶다. 단, 나무를 베는데 걸리는 시간이라는 것은 마지막으로 벤 나무를 목재가공소까지 운반하는 시간까지를 의미한다.

Input

입력 양식은 다음과 같다.

$H$ $W$
$A_{1,1}$ ... $A_{1,W}$
:
$A_{H,1}$ ... $A_{H,W}$

[입력값의 정의역]
$1 ≦ H ≦ 30$
$1 ≦ W ≦ 30$
$(H, W) ≠ (1, 1)$
$0 ≦ A_{i,j} ≦ 10000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)$
$A_{1,1}=0$

Output

조건을 만족하도록 나무를 모두 베는데 걸리는 최소 시간을 출력한다.

IO Example

입력
2 3
0 1 2
3 4 5

출력
32

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]