分数: 700 点
问题陈述
有一个 N\times N 网格,其中 N 至少是一个整数 2。对于 1\leq i,j\leq N,行中的单元格 i 从顶部和列 j 从左边开始表示为 (i,j).
最初,所有单元格都是黑色的。对于每个单元格 (i,j),成本 给出了 A_{i,j} 将单元格的颜色从黑色更改为白色。
Alice 和 Bob 使用这个网格和一个棋子玩游戏。游戏由以下三个步骤组成。
步骤 1
裁判指定棋子最初放置的单元格。
步骤 2
Alice 执行以下操作零次或多次:
- 选择黑色单元格 (i,j),支付费用 A_{i,j},并将该单元格更改为白色。
步骤 3
将棋子放在步骤 1 中指定为初始位置的单元格上。然后,从 Alice 开始,Alice 和 Bob 轮流走棋。
- 轮到爱丽丝时,爱丽丝将棋子移动到与 向左或向右.
- 轮到鲍勃时,鲍勃将棋子移动到任意一个相邻单元格中。 上、下、左或右 方向。
不允许将棋子移出网格的移动。
在 Alice 和 Bob 分别采取行动后,第 3 步立即结束 10^{10} 转。
在第 3 步结束时,如果棋子位于白色方格上,则爱丽丝获胜;如果它在黑色单元格上,则鲍勃获胜。在第 3 步中,Alice 和 Bob 各自采取最佳行动以获胜。
对于每个单元格 (h,w),找到 Alice 在第 2 步中必须支付的最小总成本,以保证获胜,如果 (h,w) 被指定为步骤 1 中的初始单元格。
T 给出了测试用例;解决它们中的每一个。 每个输入中的
约束
- 1\leq T\leq 10^4
- 2\leq N\leq 500
- 0\leq A_{i,j}\leq 10^9
- 所有输入值均为整数。
- 总和 N^2 所有测试用例最多 500^2.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
输出
输出 N 每个测试用例的行数。
对于每个测试用例, h- 第行应包含 Alice 在第 2 步中必须支付的最小总成本,以保证每个人获胜 (h,1),(h,2),\ldots,(h,N) 指定为初始单元格,以空格分隔。
示例输入 1
3 2 1 4 3 2 3 1 2 3 8 9 4 7 6 5 4 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1
示例输出 1
3 7 7 3 25 20 25 20 25 20 25 20 25 4 3 4 3 4 4 3 5 4 3 4 3 3 4 3 5
让我们解释一下第一个测试用例。
对于 (h,w) = (1,1) or (h,w) = (2,2),Alice 更改单元格 (1,1) 和 (2,2) 为白色。
在这种情况下,在鲍勃的每个回合结束时,该棋子位于 (1,1) or (2,2)。因此,在 Alice 和 Bob 分别采取后立即 10^{10} 转动,该块位于 (1,1) or (2,2),因此无论棋子如何移动,爱丽丝都会获胜。 Alice 在第 2 步中支付的成本为 A_{1,1}+A_{2,2}=1+2=3.
对于 (h,w) = (1,2) or (h,w) = (2,1),可以验证Alice可以通过改变单元格获胜 (1,2) 和 (2,1) 为白色。在这种情况下,Alice 在步骤 2 中支付的成本为 A_{1,2}+A_{2,1}=4+3=7.