← 返回题目列表

AtCoder · past202012_e

E. 邮票

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

分数: 7 点

警告

2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有一个网格 S 与 H 行和 W 方格列。让广场 (i, j) 表示 i从顶部开始的第行和 j左起第 列。
某些方格可能包含障碍物。
广场 (i, j) 包含障碍物,如果 S_{i, j} is #,并且它不包含一个 if S_{i, j} is ..

您有一个形状由网格中的正方形组成的印章 T 与 H 行和 W 列。 更具体地说,印章的形状由正方形组成 (i, j) 这样 T_{i, j} is #.
此处,形成图章的方块是相连的。 换句话说:让我们调用 Square (i, j) 有效时间 T_{i, j} is #。然后,我们可以通过重复向上、向下、向左或向右移动到一个有效方块,在任意两个有效方块之间移动。

您可以将图章移动到您喜欢的任何位置并旋转它。 确定是否可以将图章定位在网格上 S 以满足以下条件:

  • 形成图章的正方形的边缘均与网格中正方形的某些边缘平行 S;
  • 印章没有伸出网格 S;
  • 印记不占据包含障碍物的方格。

约束

  • 1 \le H \le 10
  • 1 \le W \le 10
  • H 和 W 是整数。
  • S_{i, j} is # or ..
  • T_{i, j} is # or ..
  • 方块 (i, j) 这样 T_{i, j} is # 已连接。
  • S_{i, j} is . 至少一对 (i, j).
  • T_{i, j} is . 至少一对 (i, j).

输入

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

H W
S_{1, 1}S_{1, 2}S_{1, 3}\dots S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3}\dots S_{2, W}
S_{3, 1}S_{3, 2}S_{3, 3}\dots S_{3, W}
\hspace{40pt} \vdots
S_{H, 1}S_{H, 2}S_{H, 3}\dots S_{H, W}
T_{1, 1}T_{1, 2}T_{1, 3}\dots T_{1, W}
T_{2, 1}T_{2, 2}T_{2, 3}\dots T_{2, W}
T_{3, 1}T_{3, 2}T_{3, 3}\dots T_{3, W}
\hspace{40pt} \vdots
T_{H, 1}T_{H, 2}T_{H, 3}\dots T_{H, W}

输出

如果可以定位印记以便满足所有条件,则打印 Yes;否则,打印 No.


示例输入 1

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

示例输出 1

Yes

我们可以旋转图章并将其移动到下图所示的位置来满足条件。图中,绿色部分代表印章,灰色方块包含障碍物。

Figure


示例输入 2

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

示例输出 2

No

仅通过移动和旋转图章来定位图章以满足条件是不可能的。


示例输入 3

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

示例输出 3

Yes

我们可以按如下方式放置图章:

Figure