AT_abc054_b.[ABC054B] Template Matching

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定一个 NN 行 NN 列像素排成的图像 A 和 MM 行 MM 列像素排成的图像 B。这里像素是图像的最小单位,可以看作为 1×11 \times 1 的正方形。

图像均为二进制图像,因此可以用白色和黑色这两种颜色来表示每个像素。在输入中,字符 . 表示白色像素,# 表示黑色像素。

图像 A 用 N 个字符串 A1,...,ANA_1,...,A_N 来表示。其中字符串 aia_i 的第 jj 个字符对应图像 A 中从上数第 ii 行,从左数 jj 列的像素。

同理图像 B 用 M 个字符串 B1,...,BMB_1,...,B_M 来表示。字符串 bib_i 的第 jj 个字符对应图像 B 中从上数第 ii 行,从左数 jj 列的像素。

当仅允许图像进行平行移动时,请判断图像 B 是否能被包含在图像 A 中。

输入格式

第一行两个正整数 N,MN, M。

接下来 NN 行,NN 个字符串 a1⋯aNa_1 \cdots a_N。

接下来 MM 行,MM 个字符串 b1⋯bMb_1 \cdots b_M。

输出格式

如果图像 A 中包含图像 B ,则输出 Yes,否则输出 No。

输入输出样例

  • 输入#1

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

    输出#1

    Yes
  • 输入#2

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

    输出#2

    No

说明/提示

数据范围

1≤M≤N≤501 \le M \le N \le 50

样例解释 1

因为图像 B 与图像 A 中左上角的 2×22 \times 2 子图像以及右下角的 2×22 \times 2 子图像相匹配,所以输出 Yes 。

样例解释 2

由于图像 A 由白色像素组成,图像 B 由黑色像素组成,所以图像 A 不包含图像 B。

输入解题思路,AI测评打分。不知道怎么写?

首页