ABC054-B - Template Matching を解く

ABC054-B - Template Matching

テンプレートマッチングをする問題

画像処理の勉強をしたことがある人ならば一度は書いたことがあるかもしれない

イメージとしては、テンプレート画像を探索先の画像の左上から

右端にかけて動かしていき、各領域が一致するかを確認

右端に達したら一つ下の段へ行きまた左端から…という処理を

探索先の画像の右下まで繰り返していく

テンプレート画像を上記の通り動かすためには二重ループを書く必要がある

また、各領域内でのテンプレート画像の一致を確認する際にも

テンプレート画像の幅と高さを使った二重ループを書く必要があり

結果として四重ループの少し複雑なコードになるので集中して書いていきたい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N,M=map(int,input().split())

la=[]
for i in range(N):
  la.append(input())

lb=[]
for i in range(M):
  lb.append(input())

for i in range(N-M+1):
  for j in range(N-M+1):

    f=True
    for k in range(M):
      for l in range(M):
        if la[i+k][j+l]!=lb[k][l]:
          f=False

    if f:
      print('Yes')
      exit()

print('No')

提出結果はACでした

解説スライドにもサンプルソースがあるので

実装の参考にしたい方は確認してみてください

AtCoder Beginner Contest 054 解説