#1854. [ABC054B] Template Matching

[ABC054B] Template Matching

题面翻译

给你N行N列的图像A,再给你M行M列的图像B。

每个图像都只由.#构成,分别代表白和黑。

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

题目描述

N N 行、横 N N 列に画素が並んだ画像Aと、縦 M M 行、横 M M 列に画素が並んだテンプレート画像Bが与えられます。
画素は画像を構成する最小単位であり、ここでは 1×1 1×1 の正方形とします。
また、与えられる画像は全て2値画像であり、各画素の色は白と黒の2種類で表されます。

入力において、全ての画素は文字で表されており、.は白色の画素、 # は黒色の画素に対応します。
画像Aは N N 個の文字列 A1,...,AN A_1,...,A_N で表されます。
文字列 Ai A_i j j 文字目は、画像Aの上から i i 番目、左から j j 番目の画素に対応します。(1i,jN) (1≦i,j≦N)
同様に、テンプレート画像Bは M M 個の文字列 B1,...,BM B_1,...,B_M で表されます。
文字列 Bi B_i j j 文字目は、テンプレート画像Bの上から i i 番目、左から j j 番目の画素に対応します。(1i,jM) (1≦i,j≦M)

画像の平行移動のみ許されるとき、テンプレート画像Bが画像Aの中に含まれているかを判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M A1 A_1 A2 A_2 : : AN A_N B1 B_1 B2 B_2 : : BM B_M

输出格式

画像Aの中にテンプレート画像Bを含む場合は Yes、含まない場合は No を出力せよ。

样例 #1

样例输入 #1

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

样例输出 #1

Yes

样例 #2

样例输入 #2

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

样例输出 #2

No

提示

制約

  • 1MN50 1≦M≦N≦50
  • Ai A_i #. からなる長さ N N の文字列
  • Bi B_i #. からなる長さ M M の文字列

Sample Explanation 1

テンプレート画像Bが、画像A中の左上の 2 × 2 2\ ×\ 2 の部分画像と右下の 2 × 2 2\ ×\ 2 の部分画像に一致するため、Yes と出力します。

Sample Explanation 2

画像Aは白色の画素、テンプレート画像Bは黒色の画素で構成されるため、含まれることはありません。