CF2033B Sakurako and Water

在与浩介的旅途中，樱子和浩介发现了一个山谷，这个山谷可以表示为一个大小为 $n \times n$ 的矩阵，在 $i$ 行和 $j$ 列的交点上有一座高度为 $a_{i,j}$ 的山；如果 $a_{i,j} < 0$，那么那里有一个湖。 浩介非常怕水，所以樱子需要帮助他： - 她可以用魔法选择一个**正方形**的山峰区域，并将该区域**主对角线**上的每座山峰的高度正好增加一个。 更正式地说，她可以选择一个左上角位于 $(i, j)$，右下角位于 $(p, q)$ 的子矩阵，满足 $p-i=q-j$。然后在 $(i + k)$ 行和 $(j + k)$ 列的交点处的每个元素上加 $1$，其中 $k$ 满足 $0 \le k \le p-i$。 求樱子使用魔法的最少次数，这样就没有湖泊了。

第一行包含一个整数 $t$（$1 \le t \le 200$），测试用例数。 每个测试用例的描述如下： - 每个测试用例的第一行包含一个数字 $n$（$1 \le n \le 500$）。 - 接下来的每行 $n$ 都由 $n$ 个整数组成，中间用空格隔开，这些整数对应山谷中的山高 $a$（$-10^5 \le a_{i,j} \le 10^5$）。 保证所有测试用例中 $n$ 的总和不超过 $1000$。

针对每个测试案例，输出樱子使用魔法使所有湖泊消失的最少次数。

### 样例解释 #### 样例 1 矩阵中没有负数（即没有湖），因此不需要任何魔法操作。 #### 样例 2 - 只有一个湖位于 $(1,1)$，高度为 $-1$。 - 我们需要选择一个包含 $(1,1)$ 的正方形区域，并对其主对角线上的元素加 $1$。 - 因此答案是 $1$。 #### 样例 3 - 湖位于 $(2,1)$、$(2,3)$ 和 $(3,3)$，高度分别为 $-2$、$-1$ 和 $-1$。 - 一种可能的操作步骤： 1. 选择 $2 \times 2$ 的正方形（从 $(2,1)$ 到 $(3,2)$），主对角线为 $(2,1)$ 和 $(3,2)$： - $(2,1)$ 变为 $-2 + 1 = -1$。 - $(3,2)$ 变为 $0 + 1 = 1$。 - 矩阵变为： ```test [ 1, 2, 3] [-1, 1, -1] [ 0, 1, -1] ``` 2. 选择 $1 \times 1$ 的正方形（仅 $(2,1)$），操作 $1$ 次： - $(2,1)$ 变为 $-1 + 1 = 0$。 4. 选择 $1 \times 1$ 的正方形（仅 $(2,3)$），操作 $1$ 次： - $(2,3)$ 变为 $-1 + 1 = 0$。 5. 选择 $1 \times 1$ 的正方形（仅 $(3,3)$），操作 $1$ 次： - $(3,3)$ 变为 $-1 + 1 = 0$。 - 最终矩阵： ```test [1, 2, 3] [0, 1, 0] [0, 1, 0] ``` - 总操作次数：$4$。 样例解释由 DeepSeek V3 完成。