Template Matching

题目描述

给定一个由 $N$ 行 $N$ 列像素组成的图像 $A$，以及一个由 $M$ 行 $M$ 列像素组成的模板图像 $B$。
像素是图像的最小单元，在本题中它是大小为 $1×1$ 的正方形。
此外，给定的图像是二值图像，每个像素的颜色要么是白色要么是黑色。
在输入中，每个像素用一个字符表示：$.$ 对应白色像素，# 对应黑色像素。
图像 $A$ 以 $N$ 个字符串 $A_1,...,A_N$ 给出。
字符串 $A_i$ 的第 $j$ 个字符对应图像 $A$ 的第 $i$ 行第 $j$ 列的像素 $(1≦i,j≦N)$。
同样地，模板图像 $B$ 以 $M$ 个字符串 $B_1,...,B_M$ 给出。
字符串 $B_i$ 的第 $j$ 个字符对应模板图像 $B$ 的第 $i$ 行第 $j$ 列的像素 $(1≦i,j≦M)$。
判断在只允许对图像进行平行平移的情况下，模板图像 $B$ 是否包含在图像 $A$ 中。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $:$
$A_N$ $B_1$ $B_2$ $:$
$B_M$

输出格式

如果模板图像 $B$ 包含在图像 $A$ 中则输出 $Yes$，否则输出 $No$。

3 2
#.#
.#.
#.#
#.
.#

Yes

4 1
....
....
....
....
#

No

提示

$1≦M≦N≦50$ $A_i$ 是长度为 $N$ 的由 # 和 $.$ 组成的字符串。 $B_i$ 是长度为 $M$ 的由 # 和 $.$ 组成的字符串。模板图像 $B$ 与 $A$ 的左上 $2 × 2$ 子图像以及右下 $2 × 2$ 子图像 相同。因此，输出应该是 $Yes$。
模板图像 $B$（由一个黑色像素组成）不包含在由白色像素组成的图像 $A$ 中。

标签: AtCoder|abc054B

来源

AtCoder|abc054B