Informatica Online Judge

  간선 도로 [2151 / 0867]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 14   Total Tried : 16


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

[koistudy.net (unkonwn)]

Background

GSHS시는 격자형태로 도시가 이루어져 있다.

가로로 $H$개의 도로가 존재하며, 세로로 $W$개의 도로가 존재한다.

각 도로 간의 간격은 모두 1이다.

GSHS시는 이들 $H+W$개의 도로로부터 좌우 방향으로 1개, 상하 방향으로 1개 모두 2개의 도로를 간선도로로 정하기로 했다.

위로부터 $i$번째 도로와 왼쪽으로부터 $j$번째 도로의 교차점을 ($i$, $j$)로 나타내기로 하자.

교차점 ($i$, $j$)와 위로부터 $m$개째 도로와의 거리는 |$i$-$m$|이다.

교차점 ($i$, $j$)와 왼쪽으로부터 $n$개째 도로와의 거리는 |$j$-$n$|이다.

또 교차점 ($i$, $j$) 부근에는 $A_{i,j}$ 명의 사람이 살고 있다고 한다.

2개의 간선도로를 정한다고 할 때 다음 기준을 만족해야 한다.

- GSHS시의 모든 주민들에 대하여 가장 가까운 간선도로까지의 거리의 총합을 최소화하도록 하고자 한다.

이 값 즉 최솟값을 구하는 프로그램을 작성하시오.

Input

입력 형식은 다음과 같다.

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

[입력값의 정의역]
$2 ≦ H ≦ 25$
$2 ≦ W ≦ 25$
$0 ≦ A_{i,j} ≦ 100 (1 ≦ i ≦ H, 1 ≦ j ≦ W)$

Output

조건을 만족하는 최솟값을 출력한다.

IO Example

입력
3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

출력
8

설명 : 위로부터 2번째 도로와 왼쪽으로부터 첫 번째 도로를 고르면 모든 지점에서의 거리의 합은 8이다.

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