← 返回题目列表

AtCoder · joi2018_yo_e

E. 森林砍伐

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

配点 : 100 点

問題文

JOI王国有广阔的森林。森林呈长方形形状,南北方向 H 个格子,东西方向 W 个格子被划分为网格。从北边 i 个格子,西边 j 马斯目(1 ≦ i ≦ H, 1 ≦ j ≦ W的区域有 A_{i,j} 本树木生长。然而,在西北角的区域有木材加工场,没有树木生长。也就是说,A_{1,1}=0 。

人们可以进入没有树木的区域。此外,人们可以迁移到东西南北的邻近地区,只要这些地区没有树木生长即可。你不能走出森林。 JOI君希望将砍伐树木作为JOI王国的公共项目,并让西北和东南地区之间的移动成为可能。

树木砍伐如下。首先,JOI位于木材加工厂所在的西北端区域。 JOI,您所在的区域与您当前所在的区域以及北、南、东、西区域相邻,没有树木。 您可以在 1 分钟后移动。此外,从与北、南、东、西相邻的树木生长的地区,1 分钟内树 1 这棵树可以砍掉。然而,树木 1 每砍倒一棵树,就必须将其运送到该地区西北角的木材加工厂。 JOI携带树时的移动速度不会改变。运输树木时不能砍伐其他树木。

求砍伐一棵树以满足条件所需的最短时间。然而,砍伐所需的时间定义为将最后砍伐的树木运输到木材加工厂所需的时间。

制約

  • 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

入力

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

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

出力

求砍伐一棵树以满足条件所需的最短时间。 1 行输出。

小課題 1 [15点]

  • 1 ≦ H ≦ 5
  • 1 ≦ W ≦ 5

小課題 2 [28点]

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

小課題 3 [57点]

  • 没有其他限制。

入力例 1

2 3
0 1 2
3 4 5

出力例 1

32

从北方 i 个格子,西边 j 方形面积 由 (i, j) 代表。

第一 砍倒 (1, 2) 树。这包括 需要 1 分钟。

下一步 砍掉 (1, 3) 中的所有树木。1 砍伐树木, 从(1,1) 向东 1 前进, 砍倒(1, 3) 树并向西移动。 1 前进 回到 (1,1) ,所以 需要3 分钟。因此,对于这个 2 × 3 = 6 分钟。

下一步 砍掉 (2, 3) 中的所有树木。1 砍伐树木, 从(1,1) 向东 2 前进, 砍倒(2, 3) 树并向西移动。 2 前进 回到 (1,1) ,所以 需要 5 分钟。因此,对于这个 5 × 5 = 25 分钟。

总而言之 需要 1 + 6 + 25 = 32 分钟。无法在比这更短的时间内砍伐树木来满足条件,因此 输出32 。 你只需要砍掉


入力例 2

2 5
0 5 0 0 0
0 0 0 9 1

出力例 2

13

(2, 5) 树。


入力例 3

2 5
0 2 0 0 0
0 0 0 9 1

出力例 3

11

首先, 砍倒(1, 2) 树,然后 只要砍倒 (2, 5) 树即可。