#ABC054B. Template Matching
Template Matching
题目描述
You are given an image composed of rows and columns of pixels, and a template image composed of rows and columns of pixels.
A pixel is the smallest element of an image, and in this problem it is a square of size .
Also, the given images are binary images, and the color of each pixel is either white or black.
In the input, every pixel is represented by a character: .
corresponds to a white pixel, and #
corresponds to a black pixel.
The image is given as strings .
The -th character in the string corresponds to the pixel at the -th row and -th column of the image .
Similarly, the template image is given as strings .
The -th character in the string corresponds to the pixel at the -th row and -th column of the template image .
Determine whether the template image is contained in the image when only parallel shifts can be applied to the images.
给你一幅由 行和 列像素组成的图像 和一幅由 行和 列像素组成的模板图像 。
像素是图像中最小的元素,在本问题中,像素是大小为 的正方形。
此外,给定的图像是二值图像,每个像素的颜色为白色或黑色。在输入中,每个像素用一个字符表示:
.
对应一个白色像素,#
对应一个黑色像素。
图像 的字符串为 和 。
字符串 中的 -th 字符对应图像 的 -th 行和 -th 列的像素。 .
同样,模板图像 的字符串为 。
字符串 中的 -th 字符对应模板图像 的 -th 行和 -th 列的像素。 .在只能对图像进行平行移动的情况下,确定模板图像 是否包含在图像 中。
输入格式
输入内容按以下格式标准输入:
输出格式
如果模板图像 包含在图像 中,则打印 是
。否则打印否
。
样例 #1
样例输入 #1
3 2
#.#
.#.
#.#
#.
.#
样例输出 #1
Yes
样例 #2
样例输入 #2
4 1
....
....
....
....
#
样例输出 #2
No
说明
数据规模与约定
- 是长度为 的字符串,由
#
和.
组成。 - 是长度为 的字符串,由
#
和.
组成。
样例 解释
模板图像 与 的左上方 子图像和右下方 子图像完全相同。因此,输出结果应为 "是"。
样例 解释
由黑色像素组成的模板图像 不包含在由白色像素组成的图像 中。
相关
在以下作业中: