atcoder#AGC017E. [AGC017E] Jigsaw
[AGC017E] Jigsaw
配点 : 点
問題文
個の特殊なジグソーピースがあります.それぞれのピースは,幅が で高さが 以上の長方形のパーツを つつなげた形をしています. 番目のピースは,次のような形をしています:
- 高さ のパーツの左側に高さ のパーツを,右側に高さ のパーツをくっつけた形.ただし,左側のパーツの一番下の辺,右側のパーツの一番下の辺は,それぞれ中央のパーツの一番下の辺から だけ上にある.
すぬけ君は,これらのピースを,一辺が の正方形の形をしたテーブルの上に置こうとしています.この時,次の条件を満たさなければなりません:
- すべてのピースをテーブルの上に置く.
- すべてのピースの中央のパーツの一番下の辺全体は,テーブルの手前の辺に接している.
- 左右のパーツの一番下の辺全体は,テーブルの手前の辺に接しているか,他のピースを構成するあるパーツの上の辺と接している.
- ピースを回転させたり,反転させたりして用いてはならない.
このような並べ方ができるかどうかを判定してください.
制約
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
:
出力
条件を満たすようにピースを並べることが可能なら YES
を,不可能なら NO
を出力せよ.
3 4
1 1 0 0
2 2 0 1
3 3 1 0
YES
例えば,下図のように並べればよいです.
4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
NO
10 4
1 1 0 3
2 3 2 0
1 2 3 0
2 1 0 0
3 2 0 2
1 1 3 0
3 2 0 0
1 3 2 0
1 1 1 3
2 3 0 0
YES