B - 数字パズル

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100

問題文

リクルートホールディングスの社員の間では、数字パズルが流行っています。

社員が遊んでいる数字パズルは、縦 9 行、横 9 列のマスに 1 から 9 の数字を一つずつ書いていくものです。 ただし、書かれた数字が以下の条件を満たす必要があります。

  • それぞれの行において、同じ数字は 2 度以上登場しない。
  • それぞれの列において、同じ数字は 2 度以上登場しない。
  • どのマスについても、そのマスからチェスのナイトの駒が 1 回で移動できる位置 (図参照) に、そのマスと同じ数字が書かれていない。

図. もしあなたが黒いマスにチェスのナイトの駒を置いていたならば、白い丸のある 8 箇所にのみ 1 回で移動できる。

あなたは、解答をチェックするプログラムを書くことを任されました。縦 9 行、横 9 列のマスにそれぞれ 1 から 9 の数字が書かれたものが与えられるので、それが上の条件を満たすかどうかチェックするプログラムを作成してください。

制約

  • s_{ij} (1 \leq i, j \leq 9)1 から 9 の数字

入力

入力は以下の形式で与えられる。なお、上から i 行目で左から j 列目のマスに書かれた数字が s_{ij} である。

s_{11}s_{12} ... s_{19}
:
s_{91}s_{92} ... s_{99}

出力

条件を満たすならば Yes を、満たさないならば No を出力せよ。


入力例 1

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345678

出力例 1

Yes

3 つの条件すべてを満たしています。


入力例 2

123456789
234567891
345678912
456789123
567891234
678912345
789123456
891234567
912345679

出力例 2

No

最後の行に 92 つ含まれているので、1 つ目の条件を満たしません。同様に、2 つ目の条件も満たしていません。


入力例 3

123456789
234567891
345678912
456789123
567891234
678912345
789123456
912345678
891234567

出力例 3

No

上から 7 行目で左から 3 列目のマスと上から 8 行目で左から 1 列目のマスは、互いにチェスのナイトの駒が 1 手で 移動できます。しかしこれら 2 つのマスには同じ数字が書かれているので、 3 つ目の条件を満たしていません。