AtCoder ABC 054 B – Template Matching Python解説

2021年11月21日

スポンサーリンク

Template Matching

問題文はこちらから「Template Matching」。画像Bが画像Aに含まれるかを判定する問題。入力制限も厳しくないので、for文の4重ループを使います。

n, m = map(int, input().split())

a = [input() for _ in range(n)]
b = [input() for _ in range(m)]

for i in range(n-m+1):
    for j in range(n-m+1):
        flag = True # *1
        for k in range(m):
            for l in range(m):
                if a[i+k][j+l] != b[k][l]:
                    flag = False
                    
        if flag:
            print("Yes")
            exit()
print("No")

上記のようにfor文の4重ループで書いてみました。今回の問題の注意点として、flag管理があります。


(*1)上記のコードでは、flag = Trueを用意することで、Bの画像とAの画像がすべて一致しているか、チェックしています。 Bの画像がすべて一致したら、if flagでプログラムを終了しています。これは、途中でプログラムを終了しない場合、残りのループで一致しない画像が出てくるとflagがFalseになるからです。