#P4847. [Neerc2016]Kids Designing Kids
[Neerc2016]Kids Designing Kids
题目描述
凯文和金伯莉额头上都有雀斑。他们各自把雀斑画成一幅矩形像素图,每格要么有雀斑,要么没有。
他们开玩笑说,将来两人的孩子的雀斑图可以这样得到。先将两张图作相对平移,再逐格叠加。一个位置恰有父母中的一人有雀斑时,孩子就在该位置有雀斑。图的矩形范围外视为没有雀斑。
他们希望孩子的雀斑形成特定图案,例如一道闪电。请判断能否得到给定图案。比较图案时只看雀斑的位置,可以整体平移结果使其重合。
输入格式
输入依次给出凯文、金伯莉和孩子的三幅图。第 幅图先给出一行两个整数 (),表示图的高和宽。接下来 行,每行有 个字符。字符 * 表示有雀斑,. 表示没有雀斑。
保证前两幅图各至少有一个 *。第三幅图可以没有雀斑。
输出格式
如果不能得到目标图案,输出一行 NO。
否则第一行输出 YES,第二行输出两个整数 。先对齐前两幅图的左上角,再将金伯莉的图向右移动 格、向下移动 格。负值表示向左或向上移动。按题目描述叠加后,得到的雀斑图应能经过一次整体平移与第三幅图重合。
样例 #1
输入 #1
3 3
..*
.*.
*.*
3 3
**.
..*
.*.
5 2
.*
*.
**
.*
*.
输出 #1
YES
0 2