AT_abc336_f [ABC336F] Rotation Puzzle

[problemUrl]: https://atcoder.jp/contests/abc336/tasks/abc336_f $ H $ 行 $ W $ 列のマス目があり、最初、$ 1 $ 以上 $ (H\times\ W) $ 以下の整数がちょうど $ 1 $ つずつ書き込まれています。 具体的には、$ 1\leq\ i\leq\ H $, $ 1\leq\ j\leq\ W $ について、上から $ i $ 行目かつ左から $ j $ 列目のマスには $ S_{i,j} $ が書き込まれています。 以下、上から $ i $ 行目かつ左から $ j $ 列目のマスをマス $ (i,j) $ と呼びます。 次の操作を **高々 $ 20 $ 回** （$ 0 $ 回でも良い）繰り返すことで、 任意の整数の組 $ (i,j) $ $ (1\leq\ i\leq\ H,\ 1\leq\ j\leq\ W) $ について、 マス $ (i,j) $ に $ ((i-1)\times\ W+j) $ が書き込まれている状態にできるか判定し、 できる場合は必要な操作回数の最小値を出力してください。 $ 20 $ 回以下でできない場合（何回操作を繰り返してもできない場合を含む）は $ -1 $ を出力してください。 > 操作：マス目から $ (H-1)\ \times\ (W-1) $ の長方形を選んで $ 180 $ 度回転させる。 > より厳密には、整数 $ x,y $ $ (0\ \leq\ x,\ y\ \leq\ 1) $ を選び、 > $ 1\ \leq\ i\ \leq\ H-1 $, $ 1\ \leq\ j\ \leq\ W-1 $ をみたすすべての整数の組 $ (i,j) $ について同時に、 > マス $ (i+x,j+y) $ に書かれた整数をマス $ (H-i+x,W-j+y) $ に書かれた数に書き換える。 マス目に書き込まれている整数が条件をみたしていれば良く、書き込まれている向き等は考える必要がないことに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,1} $ $ S_{1,2} $ $ \ldots $ $ S_{1,W} $ $ S_{2,1} $ $ S_{2,2} $ $ \ldots $ $ S_{2,W} $ $ \vdots $ $ S_{H,1} $ $ S_{H,2} $ $ \ldots $ $ S_{H,W} $

問題文の条件をみたすために必要な操作回数の最小値を出力せよ。 ただし、$ 20 $ 回以下の操作で条件をみたすようにできないときは $ -1 $ を出力せよ。

### 制約 - $ 3\leq\ H,W\leq\ 8 $ - $ 1\leq\ S_{i,j}\leq\ H\times\ W $ - $ (i,j)\neq\ (i',j') $ ならば $ S_{i,j}\neq\ S_{i',j'} $ - 入力はすべて整数 ### Sample Explanation 1 次の順で操作を行うことで $ 2 $ 回の操作で問題文の条件をみたすようにすることができます。 - 左上の長方形を選び、操作を行う。すなわち $ x=0 $, $ y=0 $ を選んで操作を行う。 - 右下の長方形を選び、操作を行う。すなわち $ x=1 $, $ y=1 $ を選んで操作を行う。 一方で $ 1 $ 回以下の操作でみたすようにすることは不可能であるため、$ 2 $ を出力します。  ### Sample Explanation 2 $ 20 $ 回以下の操作で条件をみたすようにすることができないため、$ -1 $ を出力します。