/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君は黒いマスと透明なマスからなるシート A,B を 1 枚ずつと、透明なマスのみからなる無限に広がるシート C を持っています。
また、高橋君には黒いマスと透明なマスからなる、理想とするシート X が存在します。
シート A,B,X の大きさはそれぞれ縦 H_A マス \times 横 W_A マス、縦 H_B マス \times 横 W_B マス、縦 H_X マス \times 横 W_X マスです。
シート A の各マスは . と # からなる長さ W_A の文字列 H_A 個 A_1,A_2,\ldots,A_{H_A} によって表され、
A_i (1\leq i\leq H_A) の j 文字目 (1\leq j\leq W_A) が、
. のときシート A の上から i 行目かつ左から j 列目のマスは透明なマスであり、
# のとき黒いマスです。
シート B,X の各マスも、同様に長さ W_B の文字列 H_B 個 B_1,B_2,\ldots,B_{H_B} および長さ W_X の文字列 H_X 個 X_1,X_2,\ldots,X_{H_X} によって表されます。
高橋君の目標は、次の手順で、シート A,B,C から、A,B に存在する すべての黒いマスを使って シート X を作り出すことです。
- シート A,B をマス目に沿ってシート C に貼り付ける。この時、シート A,B はそれぞれ好きな場所に平行移動させて貼って良いが、シートを切り分けたり、回転させたりしてはいけない。
- シート C からマス目に沿って H_X\times W_X マスの領域を切り出す。ここで、切り出されたシートの各マスは、シート A または B の黒いマスが貼り付けられていれば黒いマスに、そうでなければ透明なマスとなる。
このとき、貼り付ける位置と切り出す領域をうまくとることで高橋君は目標を達成できるか、すなわち次の条件をともにみたすことにできるか判定してください。
- 切り出されたシートはシート A,B の 黒いマスをすべて 含む。切り出されたシートの上でシート A,B の黒いマスどうしが重なって存在していても構わない。
- 切り出されたシートは、回転させたり裏返したりすることなくシート X と一致する。
制約
- 1\leq H_A,W_A,H_B,W_B,H_X,W_X\leq 10
- H_A,W_A,H_B,W_B,H_X,W_X は整数
- A_i は
.と#のみからなる長さ W_A の文字列 - B_i は
.と#のみからなる長さ W_B の文字列 - X_i は
.と#のみからなる長さ W_X の文字列 - シート A,B,X はそれぞれ少なくとも 1 つ以上の黒いマスを含む。
入力
入力は以下の形式で標準入力から与えられる。
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
出力
高橋君が問題文中の目標を達成できるならば Yes を、できないならば No を出力せよ。
入力例 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
出力例 1
Yes
まず、シート A をシート C に貼り付けると下図のようになります。
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
さらに、シート B をシート A と左上を合わせて貼ってみると下図のようになります。
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
ここで、上で具体的に図示されている範囲のうち、上から 1 行目かつ左から 2 列目のマスを左上として 5\times 3 マスを切り出すと下図のようになります。
... #.# .#. .#. ...
これはシート A,B のすべての黒いマスを含んでおり、また、シート X と一致しているため条件を満たしています。
よって、Yes を出力します。
入力例 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
出力例 2
No
シート A や B を回転させて貼ってはいけないことに注意してください。
入力例 3
1 1 # 1 2 ## 1 1 #
出力例 3
No
どのように貼ったり切り出したりしても、シート B の黒いマスをすべて含むように切り出すことはできないため、1 つめの条件をみたすことができません。
よって、No を出力します。
入力例 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
出力例 4
Yes
Score : 300 points
Problem Statement
Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.
The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.
Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.
- Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
- Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.
Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.
- The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
- The cut-out sheet coincides sheet X without rotating or flipping.
Constraints
- 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
- H_A, W_A, H_B, W_B, H_X, W_X are integers.
- A_i is a string of length W_A consisting of
.and#. - B_i is a string of length W_B consisting of
.and#. - X_i is a string of length W_X consisting of
.and#. - Sheets A, B, and X each contain at least one black square.
Input
The input is given from Standard Input in the following format:
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
Output
If Takahashi can achieve the goal described in the problem statement, print Yes; otherwise, print No.
Sample Input 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
Sample Output 1
Yes
First, paste sheet A onto sheet C, as shown in the figure below.
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.
... #.# .#. .#. ...
This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.
Therefore, print Yes.
Sample Input 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
Sample Output 2
No
Note that sheets A and B may not be rotated or flipped when pasting them.
Sample Input 3
1 1 # 1 2 ## 1 1 #
Sample Output 3
No
No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition.
Therefore, print No.
Sample Input 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
Sample Output 4
Yes