← 返回题目列表

AtCoder · abc307_c

F. 理想的床单

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

高桥有两张 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} 组成 . 和 #.
如果 j- 第一个字符 (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is .,位于 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}。

高桥的目标是创建表 X 使用 全黑方块 张 A 和 B 按照以下步骤操作 A, B,和 C.

  1. 粘贴表 A 和 B 到纸张上 C 沿着网格。每张纸都可以通过平移粘贴到任何地方,但不能剪切或旋转。
  2. 剪出一个 H_X\times W_X 工作表区域 C 沿着网格。在这里,如果黑色的正方形纸张,则剪下来的正方形纸张将是黑色的 A or 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 每个包含至少一个黑色方块。

输入

输入由标准输入按以下格式给出:

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.


示例输入 1

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

示例输出 1

Yes

一、粘贴片材 A 到纸张上 C,如下图所示。

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

接下来,粘贴表 B 使其左上角与纸张左上角对齐 A,如下图所示。

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

现在,剪出一个 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,所以你不能满足第一个条件。 因此,打印 No.


示例输入 4

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

示例输出 4

Yes