식당 개업

면접 대비

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

요약

격자의 칸마다 사는 사람 수가 주어질 때, 식당을 한 칸에 놓아 모든 사람까지의 맨해튼 거리 합이 최소가 되는 값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 행렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

사업의 성패를 결정하는 가장 중요한 요인은 입지, 입지, 입지라고 한다. Incredible Cooks Preparing Cuisine은 International City Promoting Cooking에 새 식당을 열 예정이며, 최적의 위치를 찾아 달라고 당신을 고용했다.

도시를 격자로 모델링한다. 각 칸에는 정해진 수의 사람이 살고 있다. 두 칸 $(r\_1,c\_1)$ 과 $(r\_2,c\_2)$ 의 거리는 $|r\_1-r\_2|+|c\_1-c\_2|$ 이다. 각 잠재 고객은 자신이 사는 칸에서 식당이 있는 칸까지의 최소 거리만큼 비용을 낸다. 식당 위치의 총비용은 도시의 모든 사람이 식당을 방문하는 데 드는 비용의 합이다.

주어진 도시 배치에서 식당을 최적의 위치에 열었을 때의 최소 총비용을 구하라.

입력

첫 줄에 두 정수 $n$ 과 $m$ 이 주어진다( $1 < n,m \le 50$ ). $n$ 은 격자의 행 수, $m$ 은 열 수이다.

다음 $n$ 개의 줄에는 각각 $m$ 개의 정수 $g\_{ij}$ ( $0\le g\_{ij}\le 50$ )가 주어진다. 이는 $i$ 행 $j$ 열 칸에 사는 사람의 수이다.

출력

식당을 최적의 위치에 두었을 때의 총비용을 한 개의 정수로 출력한다.

예제2

예제 1
입력
```
2 2
1 2
3 4
```
예상 출력
```
7
```
예제 2
입력
```
1 10
3 49 4 31 10 31 50 24 10 42
```
예상 출력
```
591
```