B - 10 puzzle 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : \(100\) 点

問題文

高さ\(H\)、幅\(W\)のマス目がある。はじめ、\(i\)行\(j\)列のマスには\(0\)以上\(9\)以下の数\(A_{i,j}\)が書かれている。マス目中のマスは辺を共有するマスに隣接している。ここで、あるマスの部分集合が「連結」であるとは、集合中の全てのマスのペアについて、集合中の隣接するマスに移動することを繰り返して行き来できることを指す。

カトーくんは以下の操作を\(0\)回以上行うことができる。

  • ある「連結」なマスの部分集合を選び、集合中のマスに書かれている数の最大値を\(M\)とした時、その集合の全てのマスに書かれている数を\(2 \times M\)を\(10\)で割ったあまりに書き換える。

カトーくんはマス目の全てのマスに書かれた数を\(0\)にすることができるか判定せよ。 また、\(0\)にすることができる場合、これを達成するために必要な最小の操作回数を求めよ。

制約

  • \(1 \leq H,W \leq 100\)
  • \(0 \leq A_{i,j} \leq 9\)
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

\(H\) \(W\)
\(A_{1,1}\ A_{1,2}\ \dots\ A_{1,W}\)
\(A_{2,1}\ A_{2,2}\ \dots\ A_{2,W}\)
\(\vdots\)
\(A_{H,1}\ A_{H,2}\ \dots\ A_{H,W}\)

出力

全てのマスに書かれている数を\(0\)にすることが可能な場合、以下の形式でYesと最小の操作回数\(N\)を出力してください。

Yes \(N\)

また、不可能な場合Noを出力してください。

入力例 1

2 3
0 1 2
3 4 5

出力例 1

Yes 1

例えば、全てのマスを集合として選ぶと\(M=5\)となります。\(2 \times M=10\)となり\(10\)で割ったあまりは\(0\)であるため、全てのマスの数を\(0\)に書き換えます。よって、\(1\)回の操作で目的を達成することができました。

入力例 2

2 2
1 2
2 1

出力例 2

No

どのように操作を行っても目的を達成できません。

入力例 3

5 3
6 6 6
6 5 5
6 6 6
6 5 6
6 6 6

出力例 3

Yes 2

例えば、はじめに\(6\)が書かれている全てのマスを集合として選び（これは「連結」です）これに対して操作を行った後、全てのマスを集合として選び操作を行うと\(2\)回の操作で目的を達成できます。

入力例 4

3 3
1 2 3
4 5 6
7 8 9

出力例 4

Yes 4