B3749 [语言月赛202304] Matrix

Matrix 是电影《黑客帝国》的英文名称，同样也是英文名词「矩阵」。 这是一道 **hack 题**。在此类型的题目中，你将得到**一个**问题和**一个**解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括： 1. 输出错误的结果。 2. 运行超时。 3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。 对于这一问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。 --- **提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

以下给出这道题目的叙述： 假设你处在一个 $N \times N$ 的矩阵中。矩阵左上角坐标为 $(1, 1)$，右下角坐标为 $(N, N)$。矩阵中的每个位置 $(i, j)$ 都有两个权值 $a _ {i, j}$，$b _ {i, j}$。 我们定义两点 $(x _ 1, y _ 1)$，$(x _ 2, y _ 2)$ 之间的「距离」为曼哈顿距离，即「距离」$ = |x _ 1 - x _ 2| + |y _ 1 - y _ 2|$。 我们定义你获胜，当且仅当你处在一个位置 $(x _ 0, y _ 0)$，满足这个位置与 $(N, N)$ 间的「距离」小于等于 $2$。 初始时你处在矩阵的左上角$(1, 1)$，且你手头有无限个金币。在矩阵中的每个坐标处，你可以无限次地进行如下两种操作：（假设目前你所在的坐标是 $(i, j)$） - 花费 $a _ {i, j}$ 个金币，向右移动一格（列坐标 $j$ 增加 $1$）。 - 花费 $b _ {i, j}$ 个金币，向下移动一格（行坐标 $i$ 增加 $1$）。 现在你想要知道，为了获胜，你至少需要花费多少金币。

输入共 $2N + 1$ 行。 第一行为一个整数 $N$，代表矩阵的大小。 第二行至第 $N + 1$ 行，每行 $N$ 个整数，其中第 $i + 1$ 行第 $j$ 个整数代表 $a _ {i, j}$。 第 $N + 2$ 行至第 $2N + 1$ 行，每行 $N$ 个整数，其中第 $N + i + 1$ 行第 $j$ 个整数代表 $b _ {i, j}$。

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

### 样例组与实际输入的说明 如果你直接采用『提交答案』的方式，请将输入数据命名为 `1.in`，并打成 zip 压缩包进行提交； 如果你采用提交数据生成器的方式，你的生成器应当**输出对应的输入数据**。 显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对这一问题的样例说明。 ### 数据规模要求 你给出的数据必须满足如下要求： 1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。 2. 数据中所有的数字都应为整数。 3. $1 \leq N \leq 2 \times 10 ^ 3$，$1 \leq a _ i, b _ i \leq 100$。 ### 目标代码 你需要 hack 如下的代码： ```cpp #include using namespace std; int a[2005][2005], b[2005][2005]; int f[2005][2005], n; int main() { scanf("%d", &n); for (int i = 1; i