Ideal Sheet

题目描述

Takahashi 有两张由黑格子和透明格子构成的纸 A 和 B，以及一张由透明格子构成的无限大纸 C。
还有一张 Takahashi 想要得到的理想纸 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$ 的第 $j$ 个字符 $(1\leq j\leq W_A)$ $(1\leq i\leq H_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、C 进行如下操作，使用纸 A 和 B 中的所有黑格子来制作出纸 X（强制要求使用所有黑格子）。

将纸 A 和 B 按网格贴到纸 C 上。每张纸可以通过平移任意贴到任意位置，但不能裁剪或旋转。 沿网格从纸 C 上裁切出一个 $H_X\times W_X$ 的区域。此处，被裁出的纸上的某个格子如果该位置上粘贴了纸 A 或 B 的黑格子则为黑色，否则为透明。

判定是否存在合适的粘贴位置和裁切区域，使得 Takahashi 能完成他的目标，也就是是否可以满足以下两个条件。

被裁出的纸包含纸 A 和 B 的所有黑格子。纸 A 和 B 的黑格子在被裁出的纸上可以重叠。 被裁出的纸与纸 X 在不旋转不翻转的情况下完全一致。

输入格式

输入由标准输入按以下格式给出： $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}$

输出格式

如果 Takahashi 能实现题目陈述中的目标，打印 $Yes$；否则打印 $No$。

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

Yes

     $\vdots$
  .......  
  .#.#...  
$\cdots$.......$\cdots$
  ..#....  
  .......  
     $\vdots$

     $\vdots$
  .......  
  .#.#...  
$\cdots$..#....$\cdots$
  ..#....  
  .......  
     $\vdots$

...
#.#
.#.
.#.
...

2 2
#.
.#
2 2
#.
.#
2 2
##
##

No

1 1
#
1 2
##
1 1
#

No

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

Yes

提示

$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 各自至少包含一个黑格子。首先，将纸 A 按照下图所示贴到纸 C 上。

接着，将纸 B 贴到使其左上角与纸 A 的左上角对齐，如下图所示。

现在，从上面示意图所示范围中以第一行第二列的格子为左上角，裁出一个 $5\times 3$ 的区域，如下图所示。

这样包含了纸 A 与纸 B 的所有黑格子，并且与纸 X 相符，满足条件。 因此输出 $Yes$。
注意在粘贴时纸 A 与纸 B 不能旋转或翻转。
无论如何粘贴或裁切，都无法裁出一张包含纸 B 的所有黑格子的纸，因此无法满足第一个条件。 因此输出 $No$。

标签: AtCoder|abc307C

来源

AtCoder|abc307C