AT_pakencamp_2022_day3_a Moving Piece

有一个 $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 \leq x', y' \leq 2N+1$ - 格子 $(x', y')$ 没有被设置墙。 - $|x - x'| + |y - y'| = 1$ 你的任务是，布置一些墙，使得无论棋子怎么移动，都无法到达格子 $(2N+1, N+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 \leq N \leq 300$ - 对于不等于 $(1, N+1)$ 和 $(2N+1, N+1)$ 的 $(i, j)$，都有 $1 \leq A_{i, j} \leq 10^9$。 - $A_{1, N+1} = A_{2N+1, N+1} = -1$ - 所有输入均为整数。 由 ChatGPT 5 翻译