#P4847. [Neerc2016]Kids Designing Kids

    ID: 3966 传统题 1000ms 128MiB 尝试: 16 已通过: 7 难度: 6 上传者: 标签>难度分类提高动态规划有限候选集缩减位运算异或抵消排序与序列处理双指针合并有序序列CF2100

[Neerc2016]Kids Designing Kids

题目描述

凯文和金伯莉额头上都有雀斑。他们各自把雀斑画成一幅矩形像素图,每格要么有雀斑,要么没有。

他们开玩笑说,将来两人的孩子的雀斑图可以这样得到。先将两张图作相对平移,再逐格叠加。一个位置恰有父母中的一人有雀斑时,孩子就在该位置有雀斑。图的矩形范围外视为没有雀斑。

他们希望孩子的雀斑形成特定图案,例如一道闪电。请判断能否得到给定图案。比较图案时只看雀斑的位置,可以整体平移结果使其重合。

输入格式

输入依次给出凯文、金伯莉和孩子的三幅图。第 ii 幅图先给出一行两个整数 hi,wih_i,w_i(1≤hi,wi≤10001\le h_i,w_i\le 1000),表示图的高和宽。接下来 hih_i 行,每行有 wiw_i 个字符。字符 * 表示有雀斑,. 表示没有雀斑。

保证前两幅图各至少有一个 *。第三幅图可以没有雀斑。

输出格式

如果不能得到目标图案,输出一行 NO。

否则第一行输出 YES,第二行输出两个整数 x,yx,y。先对齐前两幅图的左上角,再将金伯莉的图向右移动 xx 格、向下移动 yy 格。负值表示向左或向上移动。按题目描述叠加后,得到的雀斑图应能经过一次整体平移与第三幅图重合。

样例 #1

输入 #1

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

输出 #1

YES
0 2