← 返回题目列表

AtCoder · indeednow_2015_finalb_d

D. 网格游戏

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

問題文

Indeed 员工 A 先生玩以下游戏。

垂直长度为 H,水平长度为 W 有一个由 H×W 方块组成的二维板。 从该板的左侧开始 x (1≦x≦W) ,从上面 y (1≦y≦H) 表示为 (x,y) 。

每个方格中都写有一个非负整数。 (x,y) 中写入的数字是 P_{(x,y)} 。

在任何时间点,A 先生都在该板上的某个位置。然后,根据以下规则进行操作。

  • 你可以从当前所在的方格垂直和水平移动到相邻的方格。但是,您不能移动它以使其离开板。
  • 当您第一次访问某个方块时,您将获得等于该方块上写的数字的分数。
  • 当从你当前所在的方格移动到你尚未访问过的方格时,作为移动奖励, 获得(今いるマスに書かれている数)×(次に訪れるマスに書かれている数) 的积分。
  • 移动到已经访问过的方块时不会获得积分。

首先,A先生从起点开始。 访问 (S_x,S_y) 。 A先生按照规则自由行动,最终到达目标点,即正方形。 我想要访问 (G_x,G_y) 并完成我的活动。 请注意,一旦您访问了目标点,您可能会再次返回目标点而无需完成操作。

请输出A先生按照规则行动所能获得的最高总分。


入力

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

[重要]到目前为止,请使用以下输入格式。 我错误地将其写成了 P(x,y) 形式。 它以 P(y,x) 的形式编写。描述已更正。对于给您带来的任何不便,我们深表歉意 (16:01)。

H W
S_x S_y
G_x G_y
P_{(1,1)} P_{(2,1)} … P_{(W,1)}
P_{(1,2)} P_{(2,2)} … P_{(W,2)}
:
P_{(1,H)} P_{(2,H)} … P_{(W,H)}
  • 1 线代表板的垂直和水平长度。 2 整数 给出了 H,W (1≦H,W≦100) 用空格分隔。
  • 2 线表示起点的坐标。 2 整数 给出了 S_x,S_y (1≦S_x≦W,1≦S_y≦H) 用空格分隔。
  • 3 线代表目标点的坐标。 2 整数 给出了 G_x,G_y (1≦G_x≦W,1≦G_y≦H) 用空格分隔。
  • 4 从行 H 行提供有关每个方块中写入的数字的信息。这几天之一 i(1≦i≦H) 广场 (1,i),质量 (2,i) ,…,质量 代表 (W,i) 中写入的数字 W 整数 P_{(1,i)},P_{(2,i)},…,P_{(W,i)} 用空格分隔。
  • 任何 关于 x,y(1≦x≦W,1≦y≦H) , 在0≦P_{(x,y)}≦100 很满意。 当

出力

1 行中,打印A先生根据规则行动所能获得的最大总分。在输出末尾插入换行符。


入力例1

1 6
2 1
2 1
0 1 2 3 4 0

出力例1

30

起点和终点从左端开始 这是棋盘上的第 2 格。您在该板上可以获得的最高分数是 30 点,这里是实现它的操作示例。

  • 作为起点的正方形 访问 (2,1) 。这个方块上写的数字是 1 。此时的总分是 1 点。
  • 质量 (3,1) 。这个方块上写的数字是 2 移动奖励是 1×2 点。因此,此时的总得分为 访问 5 点。
  • 质量 (4,1) 。这个方块上写的数字是 3 移动奖励是 2×3 点。因此,此时的总得分为 访问 14 点。
  • 质量 (5,1) 。此时的总分是 访问 30 点。
  • 质量 (4,1) 。由于移动是在已经访问过的方格之间进行的,因此分数没有变化。 访问
  • 质量 (3,1) 。同样,分数也没有变化。 访问
  • 质量 (2,1) 并完成操作。分数没有变化。最终总成绩为 30 点。

入力例2

3 3
1 1
3 3
2 2 2
1 2 1
1 1 1

出力例2

33

入力例3

10 10
5 2
6 2
31 0 60 19 87 98 35 68 21 41
21 46 85 72 51 13 0 49 19 25
79 82 46 65 30 99 29 44 99 8
39 48 70 99 82 32 25 49 32 54
81 20 57 70 5 40 88 97 56 17
69 54 35 98 7 38 59 91 80 34
28 13 14 28 60 26 82 10 17 100
29 0 27 43 45 88 88 92 21 67
62 33 35 22 26 68 74 95 86 79
68 18 83 72 85 21 72 34 57 77

出力例3

370423