#P6972. [NEERC 2016] Kids Designing Kids

[NEERC 2016] Kids Designing Kids

Description

凯文和金伯利的额头上都有雀斑。

他们都在纸上画了自己的雀斑图。每幅图都是一个由像素组成的矩形:每个单元格要么有雀斑,要么没有雀斑。

他们开玩笑地提议,当他们长大、结婚并有了孩子时,孩子的雀斑图是通过以下过程产生的:

凯文和金伯利的图通过平行平移移动,然后在每个单元格中,只有当且仅当父母中有一个人在这个位置有雀斑时,孩子才有雀斑。

现在他们想知道,是否存在一个平行平移可以使他们的孩子获得特定的雀斑图(例如,一个闪电),以及这个平行平移是什么。

Input Format

第一行包含两个整数 h1h_{1}w1w_{1} (1h1,w11000)(1 \le h_{1}, w_{1} \le 1000)——凯文的雀斑图的高度和宽度。接下来的 h1h_{1} 行中的每一行由 w1w_{1} 个字符组成,字符为 *.。字符 * 表示有雀斑,而 . 表示没有雀斑。

接下来的几行以相同的格式包含金伯利的图。其高度和宽度 h2h_2w2w_2 遵循相同的约束条件。

保证凯文和金伯利各自至少有一个雀斑。

接下来的几行以相同的格式包含他们想要给孩子的图。其尺寸 h3h_{3}w3w_{3} 也遵循相同的约束条件。

Output Format

在第一行输出 YES 如果可以生成所需的图,否则输出 NO

如果答案是肯定的,那么在第二行输出两个整数 xxyy,其含义如下:如果将图像叠加,使它们的左上角重合,然后将金伯利的图向右移动 xx 个单元格(负数表示向左移动图像)和向下移动 yy 个单元格(负数表示向上移动图像),然后应用上述过程,结果图可以通过平行平移移动以与输入文件中的第三幅图重合。

3 3
..*
.*.
*.*
3 3
**.
..*
.*.
5 2
.*
*.
**
.*
*.

YES
0 2

Hint

时间限制:2 秒,内存限制:512 MB。

题面翻译由 ChatGPT-4o 提供。