← 返回题目列表

AtCoder · joi2018_yo_c

C. 主干路

中文机器翻译题面 查看原题

配点 : 100 点

問題文

JOI城市从东向西笔直延伸。 H 一条真正的公路,笔直地南北延伸。 W 道路被分成棋盘形状的部分。道路之间的距离是 1 。在JOI City,这些 H+W 从主干道出发,东西方向 1 书本,南北方向 1 本,合計 2 我们决定选择这条路作为主干道。

从北方 i 本目 (1≦i≦H) 路和从西边 j 本目 (1≦j≦W) (i,j) 。交叉点 (i,j) 和来自北方 m 本目 (1≦m≦H) 道路距离为 |i-m| 和交叉点 (i,j) 从西边 n 本目 (1≦n≦W) 道路距离为 |j-n| 。 还有,路口 (i,j) 附近的 A_{i,j} 人们住在那里。

2 当选择这条主干道时,求JOI市所有居民从最近的十字路口到最近的主干道的距离之和最小。

制約

  • 2 ≦ H ≦ 25
  • 2 ≦ W ≦ 25
  • 0 ≦ A_{i,j} ≦ 100 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

入力

输入是按以下格式从标准输入给出的。

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

出力

JOI 输出该城市所有居民从最近的十字路口到最近的主干道的最小距离总和。

小課題 1 [10点]

  • A_{i,j} = 1 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

小課題 2 [90点]

  • 没有其他限制。

入力例 1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 1

8

例如,从北方 2 从主要道路和西部 1 主干道应该是主干道。


入力例 2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5

出力例 2

164

从北方 3 从主要道路和西部 2 主干道应该是主干道。