#1854. [ABC054B] Template Matching
[ABC054B] Template Matching
题面翻译
给你N行N列的图像A,再给你M行M列的图像B。
每个图像都只由.
和#
构成,分别代表白和黑。
当仅允许图像平行移动时,请确定模板图像B是否包含在图像A中。
题目描述
縦 行、横 列に画素が並んだ画像Aと、縦 行、横 列に画素が並んだテンプレート画像Bが与えられます。
画素は画像を構成する最小単位であり、ここでは の正方形とします。
また、与えられる画像は全て2値画像であり、各画素の色は白と黒の2種類で表されます。
入力において、全ての画素は文字で表されており、.
は白色の画素、 #
は黒色の画素に対応します。
画像Aは 個の文字列 で表されます。
文字列 の 文字目は、画像Aの上から 番目、左から 番目の画素に対応します。
同様に、テンプレート画像Bは 個の文字列 で表されます。
文字列 の 文字目は、テンプレート画像Bの上から 番目、左から 番目の画素に対応します。
画像の平行移動のみ許されるとき、テンプレート画像Bが画像Aの中に含まれているかを判定してください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
画像Aの中にテンプレート画像Bを含む場合は Yes
、含まない場合は No
を出力せよ。
样例 #1
样例输入 #1
3 2
#.#
.#.
#.#
#.
.#
样例输出 #1
Yes
样例 #2
样例输入 #2
4 1
....
....
....
....
#
样例输出 #2
No
提示
制約
- は
#
と.
からなる長さ の文字列 - は
#
と.
からなる長さ の文字列
Sample Explanation 1
テンプレート画像Bが、画像A中の左上の の部分画像と右下の の部分画像に一致するため、Yes
と出力します。
Sample Explanation 2
画像Aは白色の画素、テンプレート画像Bは黒色の画素で構成されるため、含まれることはありません。