AT_arc222_c [ARC222C] 2 Directions vs 4 Directions

有一个 $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 的回合，Alice 可以将棋子移动到相邻的**左侧或右侧**的格子。 - 在 Bob 的回合，Bob 可以将棋子移动到任意相邻的**上、下、左或右**方向的格子。 棋子不能被移动到网格外。 步骤 3 在 Alice 和 Bob 各自操作完 $10^{10}$ 次后立即结束。 在步骤 3 结束时，如果棋子位于白色格子上，则 Alice 获胜；如果棋子位于黑色格子上，则 Bob 获胜。在步骤 3 中，Alice 和 Bob 都会采取最优策略以追求自己的胜利。 对于每一个起始格子 $(h, w)$，求 Alice 至少需要在步骤 2 支付多少总费用，才能保证无论 Bob 如何操作，最终获胜。 给出 $T$ 组测试用例，求解每组用例的答案。

输入从标准输入读取，格式如下： > $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$ 行，按顺序输出 $(h,1),(h,2),\ldots,(h,N)$ 作为初始格子的最小总费用，数字之间用空格分隔。

### 样例解释 1 这里对第一组测试样例做说明。 对于 $(h,w) = (1,1)$ 或 $(2,2)$，Alice 只需将 $(1,1)$ 和 $(2,2)$ 格子变为白色。 此时，每次 Bob 操作后，棋子一定在 $(1,1)$ 或 $(2,2)$。换句话说，在 Alice 和 Bob 各执行 $10^{10}$ 步后，棋子必然在 $(1,1)$ 或 $(2,2)$，因此无论怎样移动，Alice 都必赢。此时 Alice 支付的总费用为 $A_{1,1} + A_{2,2} = 1 + 2 = 3$。 对于 $(h,w) = (1,2)$ 或 $(2,1)$，可以验证 Alice 只需将 $(1,2)$ 和 $(2,1)$ 变为白色即可获胜。此时 Alice 支付的总费用为 $A_{1,2} + A_{2,1} = 4 + 3 = 7$。 ### 约束条件 - $1 \leq T \leq 10^4$ - $2 \leq N \leq 500$ - $0 \leq A_{i,j} \leq 10^9$ - 所有输入都是整数。 - 所有测试用例中 $N^2$ 的总和不超过 $500^2$。 由 ChatGPT 5 翻译