#abc307c. [abc307_c]Ideal Sheet
[abc307_c]Ideal Sheet
问题陈述
Takahashi有两张标有黑色方块和透明方块的纸张和,还有一张无限大的纸张,由透明方块组成。
还有一张理想的纸张,由黑色方块和透明方块组成。
纸张、和的尺寸分别为行 列、行 列和行 列。
纸张的方块由个长度为的字符串表示,其中包含 .
和 #
。
如果 的第个字符是 .
, 则从上往下数第行、从左往右数第列的方块是透明的;如果是 #
,则该方块为黑色。
类似地,纸张和的方块分别由个长度为的字符串和个长度为的字符串表示。
Takahashi的目标是使用纸张和中的所有黑色方块,按照以下步骤使用纸张、和来创建纸张。
- 将纸张和沿着网格粘贴到纸张上。每张纸都可以通过平移来粘贴在任何地方,但不可剪切或旋转。
- 沿着网格从纸张上切出一个 的区域。在这里,如果粘贴了纸张或的黑色方块,则切割出的纸张上对应方块为黑色,否则为透明。
确定Takahashi是否可以通过适当选择纸张的粘贴位置和切割区域实现他的目标,即是否可以满足以下两个条件。
- 切割区域包含纸张和的所有黑色方块。纸张和的黑色方块可能在切割区域上重叠。
- 切割出的纸张与纸张完全一致,没有旋转或翻转。
约束条件
- 都是整数。
- 是一个长度为的字符串,由
.
和#
组成。 - 是一个长度为的字符串,由
.
和#
组成。 - 是一个长度为的字符串,由
.
和#
组成。 - 纸张、和中至少包含一个黑色方块。
输入格式
输入以以下格式从标准输入中给出:
输出格式
如果Takahashi能够实现问题描述中的目标,则输出Yes
;否则输出No
。
样例输入1
3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...
样例输出1
Yes
首先,将纸张粘贴到纸张上,如下图所示。
$\\vdots$
.......
.#.#...
.......
..#....
.......
接下来,将纸张粘贴到纸张的左上角对齐位置,如下图所示。
$\\vdots$
.......
.#.#...
..#....
..#....
.......
现在,从上面这个图中切割出一个 的区域,切割出的纸张如下图所示。
...
#.#
.#.
.#.
...
这个切割出的纸张包含了纸张和的所有黑色方块,并且与纸张完全一致,满足了条件。
因此,输出Yes
。
样例输入2
2 2
#.
.#
2 2
#.
.#
2 2
##
##
样例输出2
No
请注意,在粘贴纸张时,不能旋转或翻转纸张和。
样例输入3
1 1
#
1 2
##
1 1
#
样例输出3
No
无论如何粘贴或切割,都无法切割出包含纸张的所有黑色方块的纸张,因此无法满足第一个条件。因此,输出No
。
样例输入4
3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###
样例输出4
Yes