Score : $300$ points

问题描述

Takahashi 拥有两张由黑色正方形和透明正方形组成的纸张 $A$ 和 $B$，以及一张无限大的、由透明正方形组成的纸张 $C$。 此外，他还有一张理想的参照纸张 $X$，同样由黑色正方形和透明正方形组成。

纸张 $A$、$B$ 和 $X$ 的尺寸分别为 $H_A$ 行 $\times$ $W_A$ 列，$H_B$ 行 $\times$ $W_B$ 列，以及 $H_X$ 行 $\times$ $W_X$ 列。 纸张 $A$ 上的正方形由 $H_A$ 个长度为 $W_A$ 的字符串表示，分别为 $A_1, A_2, \ldots, A_{H_A}$，包含字符 . 和 #。 如果 $A_i$（$1\leq i\leq H_A$）的第 $j$ 个字符 $(1\leq j\leq W_A)$ 是 ., 那么从上到下第 $i$ 行、从左到右第 $j$ 列的正方形是透明的；如果是 #，则该正方形为黑色。 类似地，纸张 $B$ 和 $X$ 上的正方形分别由 $H_B$ 个长度为 $W_B$ 的字符串 $B_1, B_2, \ldots, B_{H_B}$ 和 $H_X$ 个长度为 $W_X$ 的字符串 $X_1, X_2, \ldots, X_{H_X}$ 表示。

Takahashi 的目标是通过以下步骤使用纸张 $A$ 和 $B$ 中的所有黑色正方形来制作出纸张 $X$，操作对象包括纸张 $A$、$B$ 和 $C$。

1. 将纸张 $A$ 和 $B$ 沿网格贴在纸张 $C$ 上。每张纸可以通过平移贴在任何位置，但不能裁剪或旋转。
2. 沿着网格从纸张 $C$ 上裁剪出一个 $H_X\times W_X$ 的区域。这里的裁剪部分，如果贴有纸张 $A$ 或 $B$ 的黑色正方形，则为黑色；否则为透明。

判断 Takahashi 是否能通过合理选择纸张的粘贴位置及裁剪区域来实现他的目标，即他是否能让以下两个条件同时满足：

• 裁剪出的纸张中包含了纸张 $A$ 和 $B$ 的所有黑色正方形。纸张 $A$ 和 $B$ 的黑色正方形在裁剪纸上可能重叠。
• 裁剪出的纸张在不旋转或翻转的情况下与纸张 $X$ 完全一致。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

1. 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.
2. 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

update @ 2024/3/10 08:41:26