← 返回题目列表

AtCoder · pakencamp_2022_day3_a

A. 移动件

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

配点 : 100 点

問題文

2N+1 行、2N+1 有一个列网格。从上面 i 行,从左开始 j 标记列中的方块。 (i,j) 。 所有满足

另外,(2N+1) \times (2N+1) 整数行列 A 。 对于

这里,质量 除了 (1,N+1),(2N+1,N+1) 之外,每个方格都可以放置墙。 在 (i,j) 上放置一堵墙成本 需要是 您也可以写 A_{i,j} 。

现在质量 一块被放置在 (1,N+1) 上。该棋子可以多次移动到与其当前所在方格相邻的方格(垂直、水平或垂直且没有墙)。

严格来说,质量 当棋子被放置在 (x,y) 上时, 您可以移动到 (x',y') 且满足以下所有条件的方格。

  • 1 \le x',y' \le 2N+1
  • 质量 从 (x',y') 没有安装墙壁。
  • |x-x'|+|y-y'| = 1

通过放置一些墙,您可以控制质量 我想防止 (2N+1,N+1) 无法访问。此时,找出所放置的墙的成本之和可能最小。 最大化

制約

  • 1 \le N \le 300
  • (1,N+1),(2N+1,N+1) 不是 (i,j) , 当我输入 1 \le A_{i,j} \le 10^9
  • A_{1,N+1} = A_{2N+1,N+1} = -1
  • 所有输入均为整数

入力

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

N
A_{1,1} A_{1,2} \cdots A_{1,2N+1}
A_{2,1} A_{2,2} \cdots A_{2,2N+1}
\vdots
A_{2N+1,1} A_{2N+1,2} \cdots A_{2N+1,2N+1}

出力

打印答案。 来自


入力例 1

1
1 -1 5
2 4 6
3 -1 7

出力例 1

10

入力例 2

2
8 1 -1 5 5
7 4 9 9 3
3 2 1 1 8
4 4 3 3 4
3 5 -1 5 8

出力例 2

10