C - 2 Directions vs 4 Directions Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

N\times N のマス目があります．ここで N は 2 以上の整数です．1\leq i,j\leq N に対して，上から i 行目，左から j 列目のマスを (i,j) で表します．

はじめ，すべてのマスは黒マスです．また各マス (i,j) について，マスの色を黒から白に変更するためのコスト A_{i,j} が与えられます．

このマス目とひとつの駒を使って，Alice と Bob がゲームを行います．ゲームは次のような 3 つのステップからなります．

ステップ 1

審判が，駒を最初に置くマスを指定します．

ステップ 2

Alice は次の操作を 0 回以上行います．

  • 黒マス (i,j) をひとつ選び，コスト A_{i,j} を支払って，そのマスを白マスに変更する．

ステップ 3

ステップ 1 で初期位置として指定されたマスに駒を置きます．その後 Alice から始めて，Alice と Bob は交互に手番を行います．

  • Alice の手番では，Alice が駒を左右のいずれかに隣接するマスへ動かす．
  • Bob の手番では，Bob が駒を上下左右のいずれかに隣接するマスへ動かす．

ただし，マス目の外へ出るように動かすことはできません．

ステップ 3 は，Alice と Bob がそれぞれ 10^{10} 回ずつ手番を行った直後に終了します．

ステップ 3 が終了した時点で，駒があるマスが白マスならば Alice の勝ち，黒マスならば Bob の勝ちとなります．Alice と Bob はステップ 3 において，それぞれ自分が勝つために最適に行動します．

各マス (h,w) について，ステップ 1 で駒を最初に置くマスとして (h,w) が指定された場合に，Alice が勝つためにステップ 2 で支払う必要がある合計コストの最小値を求めてください．

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 行目には，(h,1),(h,2),\ldots,(h,N) が指定された場合に，Alice が勝つためにステップ 2 で支払う必要がある合計コストの最小値を，空白区切りで出力してください．

入力例 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

1 番目のテストケースについて説明します．

(h,w) = (1,1) または (h,w) = (2,2) の場合には，Alice はマス (1,1), (2,2) を白マスに変更します．

この場合，Bob が手番を終えるたびに，駒は (1,1) または (2,2) にあります．したがって Alice と Bob がそれぞれ 10^{10} 回ずつ手番を行った直後には駒が (1,1) または (2,2) にあるため，どのように駒を動かしても，Alice の勝ちとなります．Alice がステップ 2 で支払うコストは，A_{1,1}+A_{2,2}=1+2=3 です．

(h,w) = (1,2) または (h,w) = (2,1) の場合にも，Alice はマス (1,2), (2,1) を白マスに変更することで勝てることが確かめられます．この場合，Alice がステップ 2 で支払うコストは，A_{1,2}+A_{2,1}=4+3=7 です．

Score : 700 points

Problem Statement

There is an N\times N grid, where N is an integer at least 2. For 1\leq i,j\leq N, the cell at row i from the top and column j from the left is denoted by (i,j).

Initially, all cells are black. For each cell (i,j), a cost A_{i,j} to change the color of the cell from black to white is given.

Alice and Bob play a game using this grid and one piece. The game consists of the following three steps.

Step 1

The referee specifies the cell where the piece is initially placed.

Step 2

Alice performs the following operation zero or more times:

  • Choose a black cell (i,j), pay cost A_{i,j}, and change that cell to white.

Step 3

Place the piece on the cell specified as the initial position in Step 1. Then, starting with Alice, Alice and Bob take turns making moves.

  • On Alice's turn, Alice moves the piece to an adjacent cell to the left or right.
  • On Bob's turn, Bob moves the piece to an adjacent cell in any of the up, down, left, or right directions.

A move that would take the piece outside the grid is not allowed.

Step 3 ends immediately after Alice and Bob have each taken 10^{10} turns.

At the end of Step 3, if the piece is on a white cell, Alice wins; if it is on a black cell, Bob wins. In Step 3, Alice and Bob each act optimally to win.

For each cell (h,w), find the minimum total cost that Alice must pay in Step 2 to guarantee a win if (h,w) is specified as the initial cell in Step 1.

T test cases are given; solve each of them.

Constraints

  • 1\leq T\leq 10^4
  • 2\leq N\leq 500
  • 0\leq A_{i,j}\leq 10^9
  • All input values are integers.
  • The sum of N^2 over all test cases is at most 500^2.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

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}

Output

Output N lines per test case.

For each test case, the h-th line should contain the minimum total cost that Alice must pay in Step 2 to guarantee a win for each of (h,1),(h,2),\ldots,(h,N) specified as the initial cell, space-separated.

Sample Input 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

Sample Output 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

Let us explain the first test case.

For (h,w) = (1,1) or (h,w) = (2,2), Alice changes cells (1,1) and (2,2) to white.

In this case, at the end of each of Bob's turns, the piece is at (1,1) or (2,2). Therefore, immediately after Alice and Bob have each taken 10^{10} turns, the piece is at (1,1) or (2,2), so Alice wins regardless of how the piece is moved. The cost Alice pays in Step 2 is A_{1,1}+A_{2,2}=1+2=3.

For (h,w) = (1,2) or (h,w) = (2,1), it can be verified that Alice can win by changing cells (1,2) and (2,1) to white. In this case, the cost Alice pays in Step 2 is A_{1,2}+A_{2,1}=4+3=7.