← 返回题目列表

Codeforces · 2033/B

B. 樱子和水

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

在与 Kosuke 的旅程中,Sakurako 和 Kosuke 发现了一个山谷,可以表示为大小为 $$$n \times n$$$ 的矩阵,其中第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点是一座高度为 $$$a_{i,j}$$$ 的山。如果 $$$a_{i,j} < 0$$$,则那里有一个湖。

小介非常怕水,所以樱子需要帮助他:

- 凭借她的魔法,她可以选择一个正方形的山脉区域,并将该区域主对角线上的每座山脉的高度增加一倍。

更正式地说,她可以选择一个左上角位于 $$$(i, j)$$$ 且右下角位于 $$$(p, q)$$$ 的子矩阵,这样 $$$p-i=q-j$$$。然后,对于所有 $$$k$$$,她可以向第 $$$(i + k)$$$ 行和第 $$$(j + 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

4
1
1
2
-1 2
3 0
3
1 2 3
-2 1 -1
0 0 -1
5
1 1 -1 -1 3
-3 1 4 4 -4
-1 -1 3 0 -5
4 5 3 -3 -1
3 1 -3 -1 5

输出 #1

0
1
4
19