問題一覧 > 通常問題

No.870 無敵囲い

レベル : / 実行時間制限 : 1ケース 0.300秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 321
作問者 : tkr987tkr987 / テスター : yuki2006yuki2006
4 ProblemId : 3273 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-14 13:45:56

問題文

学校のイベントで将棋の大会が開催されることになりました。 一二三君は将棋の大会で1位を取るためにインターネットで無敵囲いという陣形を調べました。
無敵囲いとは$9\times9$マスの将棋盤に配置された駒のうち3つの駒を以下のルールで動かした陣形のことを言います。

無敵囲いの定義:
座標$(2,8), (3,9), (7,9)$に初期配置されていた駒をA、B、Cとする。
駒Aを座標$(5,8)$まで動かし、駒Bを座標$(4,8)$まで動かし、駒Cを座標$(6,8)$まで動かす。
この3つの駒の配置を無敵囲いとする。

将棋の大会に参加した一二三君は$i$手目に座標$(x_{i1}, y_{i1})$の駒を$(x_{i2}, y_{i2})$に動かしました。
$N$手後の駒の配置が無敵囲いかどうか判定するプログラムを書いてください。
つまり、座標(2,8),(3,9),(7,9)に初期配置されていたそれぞれの駒が、$i$手目の移動を元にそれぞれ最終的に座標(5,8),(4,8),(6,8)になっているか判定してください。

なお、テストケースは1つの座標に駒が重複しないことが保証されます。つまり、既に駒が置かれている座標に重ねるようにして別の駒を動かすことはありません。
また、テストケースは将棋の正式な手順ではありません。

入力

$N$
$x_{11}$ $y_{11}$ $x_{12}$ $y_{12}$
$x_{21}$ $y_{21}$ $x_{22}$ $y_{22}$
...
$x_{N1}$ $y_{N1}$ $x_{N2}$ $y_{N2}$

・$3 \le N \le 20$
・$1 \le x_{i1}, x_{i2}, y_{i1}, y_{i2} < 10$
・入力は全て整数

出力

$N$手後の駒の配置が無敵囲いならYESを出力し、そうでなければNOを出力してください。

サンプル

サンプル1
入力
3
7 9 6 8
2 8 5 8
3 9 4 8
出力
YES

駒を動かす順番は関係なく、$N$手後の駒の配置が無敵囲いでさえあれば良いです。

サンプル2
入力
7
3 9 3 8
4 9 4 8
3 8 4 9
4 9 5 8
4 8 4 9
2 8 4 8
7 9 6 8
出力
NO

無敵囲いは座標$(3,9)$に初期配置されていた駒Bを座標$(5,8)$まで動かした陣形ではなく、座標$(2,8)$に初期配置されていた駒Aを座標$(5,8)$まで動かした陣形です。

サンプル3
入力
8
7 7 7 6
5 9 5 8
5 8 5 9
2 8 1 8
7 9 6 8
1 8 5 8
1 9 1 8
3 9 4 8
出力
YES

$3 < N$のとき、最終目標である無敵囲いの駒配置にするのに様々な動かし方が考えられます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。