No.228 ゆきこちゃんの 15 パズル

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 121
作問者 : 💩💩

10 ProblemId : 247 / 出題時の順位表

問題文

ゆきこちゃんは「15 パズル」というパズルで遊んでいる。
15 パズルのルールを以下に示す。

4×4 マスの盤上に、1 から 15 までの数が書かれた駒を順に並べる(下図)。
空きマスの上下左右に隣接した駒を、空きマスにスライドして動かすことを繰り返す。
目標となる駒の配置を作ることができれば成功である。



ゆきこちゃんは 15 パズルの普通の遊び方に飽きてしまった。
そこで、新たに次のルールを追加して遊ぶことにした。

ルール : 一度スライドした駒は再びスライドできない

さて、目標となる駒の配置が与えられたとき、その配置を作ることができるか判定せよ。

入力

$a_{11}$ $a_{12}$ $a_{13}$ $a_{14}$
$a_{21}$ $a_{22}$ $a_{23}$ $a_{24}$
$a_{31}$ $a_{32}$ $a_{33}$ $a_{34}$
$a_{41}$ $a_{42}$ $a_{43}$ $a_{44}$

目標となる駒の配置が与えられる。
$a_{ij}$ は 0 から 15 までの相異なる整数である。
ただし、0 は空きマスを表す。
例えば、初期配置はサンプル 1 のように入力される。

出力

目標となる駒の配置を作ることができるならば Yes を、できないならば No を出力せよ。
最後に改行してください。

サンプル

サンプル1
入力
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
出力
Yes

初期配置がそのまま目標の配置である。

サンプル2
入力
1 2 3 4
5 6 7 8
9 10 12 0
13 14 11 15
出力
Yes

サンプル3
入力
1 2 3 4
5 6 7 8
9 10 12 15
13 14 11 0
出力
No

目標の配置を作るためには、15 の駒を最低 2 回はスライドしなければならない。

提出ページヘ