縦 4 マス x 横 10 マスの長方形からなる盤面を考えます。 縦 1 マス x 横 1 マスぶんの正方形をブロックと呼びます。
ブロックを 4 つ繋げたものをテトロミノと呼び、以下の 7 種類(およびこれらに対して 90 度回転を任意回行ったもの)があります。
さて、盤面のうち 28 個のマスにブロックが置かれた状態を考えます。
左の図のように、各ブロック(赤色で表される)はマスに合うように置かれます。右の図のように半端な位置に置かれることはありません。
4 つのテトロミノ t_1, t_2, t_3, t_4 が与えられるので、このうちちょうど 3 つを選んですきな位置に置くことで、盤面全体にブロックが置かれた状態にできるか判定してください。
ただし、テトロミノを配置するにあたり、以下の条件をすべて満たさなければなりません。
盤面が n 個与えられるので、各盤面についてこの判定を行い、盤面全体にブロックを置けるならば Yes
、不可能ならば No
を出力してください。
t_1 t_2 t_3 t_4 n B_1 … B_n
はじめに、使えるテトロミノ t_1, t_2, t_3, t_4 が与えられます。 各 t_i (1 \leq i \leq 4) は以下の形式で与えられます。
h w s_1 … s_h
これはテトロミノを含む縦 h x 横 w マスの長方形であり、テトロミノの形状は s_1 … s_h で表されます。長方形のうち、テトロミノを表す部分は #
、それ以外の部分は .
で表されます。各長方形に #
はちょうど 4 つ含まれます。.
のみからなる行または列は存在しません。
次に、盤面の個数 n が与えられます。
その後、4\times 10 マスで表される盤面 B が n 個与えられます。
ブロックがある位置が #
、ない位置が .
で示されます。
#
はちょうど 28 個存在するたとえば、以下のようなテトロミノは与えられない。
3 3 ..# .#. ##.
(連結でないブロックがあり、これは上で述べたテトロミノの条件を満たさない)
3 3 ... .#. ###
(一番上の行が .
のみからなる)
n 行にわたって出力してください。i 行目には盤面 B_i に対する判定結果を Yes
または No
で出力してください。
2 3 ##. .## 2 3 #.. ### 1 4 #### 2 3 ### .#. 2 ####....## ####...### ####..#### ####...### ###..##### ###...#### ###...#### ###....###
Yes Yes
t_1, t_2, t_3, t_4 に相当するテトロミノが置かれる場所をそれぞれ 1
, 2
, 3
, 4
で示すと、各盤面は次のように敷き詰められます。
####3333## ####444### ####24#### ####222###
###11##### ###211#### ###222#### ###3333###
各盤面について、別々のテトロミノを選んで構いません。
1 4 #### 1 4 #### 2 2 ## ## 2 2 ## ## 4 ######.... ....###### #######..# #######..# ....###### ######.... ....###### ########## ######.#.# ######.#.# ##..##.#.# ##..##.#.# ##.###.#.# #.#.###.## #.#.###.## ##.###.#.#
Yes No No No
####
が足りないため、2 つ目の盤面をブロックで敷き詰めることはできません。
また、テトロミノを回転させることはできないので、3 つ目の盤面を敷き詰めることもできません。
また、4 つ目の盤面のようなブロックの配置の仕方もありえることに注意してください。すなわち、入力で与えられる盤面はテトロミノを組み合わせて作られる盤面とは限りません。