AT_abc347_g [ABC347G] Grid Coloring 2

[problemUrl]: https://atcoder.jp/contests/abc347/tasks/abc347_g $ N\times\ N $ のマス目があり、それぞれのマスには $ 0 $ 以上 $ 5 $ 以下の整数が書かれています。 上から $ i $ 行目、左から $ j $ 列目 $ (1\leq\ i,j\leq\ N) $ のマスをマス $ (i,j) $ と表し、マス $ (i,j) $ には整数 $ A\ _\ {i,j} $ が書かれています。 このマス目に対して、次の操作を $ 0 $ 回以上好きな回数行います。 - $ 0 $ が書かれているマス $ (i,j) $ と $ 1 $ 以上 $ 5 $ 以下の整数 $ x $ を $ 1 $ つ選ぶ。選ばれたマスに書かれている数を $ x $ に変更する。 操作が終了したあと、マス $ (i,j) $ に書かれている整数を $ B\ _\ {i,j} $ とします。 マス目の**コスト**を、隣接するマスに書かれた整数の差の二乗の総和とします。つまり、コストは次の式で表されます。 $ \displaystyle\sum\ _\ {i=1}\ ^\ N\sum\ _\ {j=1}\ ^\ {N-1}(B\ _\ {i,j}-B\ _\ {i,j+1})^2+\sum\ _\ {i=1}\ ^\ {N-1}\sum\ _\ {j=1}\ ^\ N(B\ _\ {i,j}-B\ _\ {i+1,j})^2 $操作が終了したあとのマス目としてありえるもののうち、コストが最小のものを求めてください。 ただし、コストが最小となるマス目の状態が複数ある場合、そのうちどれを出力しても構いません。

N/A

N/A

### 制約 - $ 1\leq\ N\leq20 $ - $ 0\leq\ A\ _\ {i,j}\leq\ 5\ (1\leq\ i\leq\ N,1\leq\ j\leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 与えられるマス目は以下のようになります。 !\[\](https://img.atcoder.jp/abc347/0748d5e94455d9f4c627617596f61af6.png) 図の右の状態になるように操作を行うことで、コストが $ 2\ ^\ 2\times6+1\ ^\ 2\times18+0\ ^\ 2\times16=42 $ となります。 コストが $ 41 $ 以下になることはないので、この状態に対応する $ B\ _\ {i,j} $ を出力することで正解になります。 ### Sample Explanation 2 はじめからコストが $ 0 $ なので、操作を行わないことでコストが最小になります。 操作が終了した後のマスの状態のうちコストが最小のものが複数ある場合どれを出力しても構わないため、 ``` 2 2 2 2 2 2 2 2 2 ``` のように出力しても正解となります。