#1781. [语言月赛202304] Matrix

[语言月赛202304] Matrix

题目描述

以下给出这道题目的叙述:

假设你处在一个 N×NN \times N 的矩阵中。矩阵左上角坐标为 (1,1)(1, 1),右下角坐标为 (N,N)(N, N)。矩阵中的每个位置 (i,j)(i, j) 都有两个权值 ai,ja _ {i, j},bi,jb _ {i, j}。

我们定义两点 (x1,y1)(x _ 1, y _ 1),(x2,y2)(x _ 2, y _ 2) 之间的「距离」为曼哈顿距离,即「距离」=∣x1−x2∣+∣y1−y2∣ = |x _ 1 - x _ 2| + |y _ 1 - y _ 2|。

我们定义你获胜,当且仅当你处在一个位置 (x0,y0)(x _ 0, y _ 0),满足这个位置与 (N,N)(N, N) 间的「距离」小于等于 22。

初始时你处在矩阵的左上角(1,1)(1, 1),且你手头有无限个金币。在矩阵中的每个坐标处,你可以无限次地进行如下两种操作:(假设目前你所在的坐标是 (i,j)(i, j))

  • 花费 ai,ja _ {i, j} 个金币,向右移动一格(列坐标 jj 增加 11)。
  • 花费 bi,jb _ {i, j} 个金币,向下移动一格(行坐标 ii 增加 11)。

现在你想要知道,为了获胜,你至少需要花费多少金币。

输入格式

输入共 2N+12N + 1 行。

第一行为一个整数 NN,代表矩阵的大小。
第二行至第 N+1N + 1 行,每行 NN 个整数,其中第 i+1i + 1 行第 jj 个整数代表 ai,ja _ {i, j}。
第 N+2N + 2 行至第 2N+12N + 1 行,每行 NN 个整数,其中第 N+i+1N + i + 1 行第 jj 个整数代表 bi,jb _ {i, j}。

输出格式

输出一行一个整数,代表为了获胜需要花费的最小硬币数量。

样例

4
1 9 2 6
4 2 8 3
2 3 2 4
2 2 3 8
9 2 8 7
1 4 6 6
2 6 5 1
8 7 3 7
10

题目来源:洛谷 B3749