#P2165. [ABC054B] Template Matching

    ID: 4515 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>语言入门数组基础算法枚举ATCoder

[ABC054B] Template Matching

题目描述

给定纵 NN 行,横 NN 列像素排列的图像 AA,纵 MM 行,横 MM 列像素排列的模板图像 BB。像素是构成图像的最小单位,即 1×11×1 的正方形。另外,给定的图像全部是二值图像,各像素的颜色用白和黑两种表示。

在输入中,全部的像素用字符表示,. 表示白色的像素,# 表示黑色的像素。图像 AANN 个字符串 A1A_1......ANA_N 表示。字符串 AiA_ijj 字符目对应于图像 AA 上第 ii、从左边第 jj 个像素。(1i,jN)(1≤i, j≤N) 同样,模板图像 BBMM 个字符串 B1B_1......BMB_M 表示。字符串 BiB_ijj 字符目对应于模板图像 BB 上第 ii、从左边第 jj 的像素。(1i,jM)(1≤i, j≤M)

当仅允许图像平行移动时,请确定模板图像 BB 是否包含在图像 AA 中。

输入格式

第一行两个正整数 N,MN, M1N,M501 \le N, M \le 50

接下来是一个 N×NN \times N 的字符矩阵,表示图像 AA

接下来是一个 M×MM \times M 的字符矩阵,表示模板图像 BB

输出格式

如果模板图像 BB 包含在图像 AA 中,则输出 Yes,否则输出 No

3 2
#.#
.#.
#.#
#.
.#
Yes
4 1
....
....
....
....
#
No