No.460 裏表ちわーわ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 40
作問者 : (⋈◍>◡<◍)。✧♡(⋈◍>◡<◍)。✧♡ / テスター : kroton 💸kroton 💸

4 ProblemId : 1121 / 出題時の順位表

問題文

ちわわは算数の天才だが、最近衰えを感じている。
このままではいけないと思ったちわわは、あるパズルを毎朝することにした。

  • 盤面は縦M×横Nマスである。
  • マスは表が白、裏が黒で、初期状態では何枚かがひっくり返っている。
  • あるマスをひっくり返すと、それに同期して8近傍の周囲のマスがひっくり返る。
    (端の場合は周囲のひっくり返せるマスのみ)
  • このゲームの目的は、最短手順で全てのマスを表向きにすることである。
ちわわの親であるあなたは、ちわわより先にこのゲームの答えを弾きだそうと考えた。
全てのマスを表向きにする最短の手順数を答えよ。
もしそのような手順が存在しない場合、"Impossible"と出力せよ。

入力

M N
\(\begin{array}{cccc}
    a_{ 1,1 } & a_{ 1,2 } & \ldots & a_{ 1,N } \\
    a_{ 2,1 } & a_{ 2,2 } & \ldots & a_{ 2,N } \\
    \vdots & \vdots & \ddots & \vdots \\
    a_{ M,1 } & a_{ M,2 } & \ldots & a_{ M,N }
\end{array}\)

\(a_{ i,j }\)は、盤面の\(i\)行目\(j\)列目を指し、表ならば0, 裏ならば1である。

\( 1 \leq M,N \leq 8 \)

出力

全てのマスをひっくり返す手順数が存在するならばその最短手順数を、存在しないならば"Impossible"を出力せよ。

サンプル

サンプル1
入力
5 5
0 0 1 1 1
0 0 1 1 1
1 1 0 1 1
1 1 1 0 0
1 1 1 0 0
出力
2

4行目2列目と2行目4列目の2マスをひっくり返すのが最短手順である。

サンプル2
入力
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
出力
16

サンプル3
入力
8 5
0 0 1 1 1
0 0 1 1 1
0 1 0 0 1
1 0 0 1 0
1 1 1 0 0
1 0 1 0 1
0 1 0 0 1
0 0 1 1 1
出力
5

提出ページヘ