4094 - 图片匹配

题目描述

在一次计算机视觉的研究项目中,研究员需要判断一张大图中是否存在另一张模板图案。

大图和模板图案都是由二维像素矩阵表示的。每个图像中的像素点可以是白色或黑色。大图 A 是一个 N \times N 的二值矩阵,模版图 B 是一个 M \times M 的二值矩阵。二值矩阵中,白色像素用字符 . 表示,黑色像素用字符 # 表示。

判断大图 A 中是否存在模版图案 B 的方法是:在大图中,如果能取出 M \times M 的子矩阵,且该子矩阵与模版 B 完全相同,则视为大图中存在模版图案 B

输入

输入包含两部分,第一部分是大图的大小和内容,第二部分是模板图案的大小和内容:

第一行:两个整数 NM,表示大图 A 和模板 B 的大小。

接下来的 N 行:表示大图 A 的每一行,其中每一行是由字符 #. 组成的字符串。

接下来的 M 行:表示模板 B 的每一行,其中每一行是由字符 #. 组成的字符串。

输出

如果大图 A 中存在模版图案 B,则输出 Yes,否则输出 No

样例

输入

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

输出

Yes

输入

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

输出

No
说明

样例 1 说明

在大图 A 中,从 1,1 点开始取大小为 2 \times 2 的子图,和模版 B 相同,输出 Yes

数据范围

对于 100\% 的数据,满足: 1 \leq M \leq N \leq 50,且所有字符都是 #.

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 入门


上一题 下一题