AtCoder Beginner Contest 054 B – Template Matching をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 054 B – Template Matching

頑張って一致するところを探すだけ。
ベタにループを回しても、制約は緩いので十分に間に合う。

# AtCoder Beginner Contest 054 B - Template Matching
# https://atcoder.jp/contests/abc054/tasks/abc054_b
# tag: グリッド 基礎問題

# 制限が 1 <= M <= N <= 50 なので、左上をあわせて
# 一致しているかどうかを確認する、素朴な全探索 O(N^2 * M^2) で
# 十分間に合う。よって、グリッドの中から目標と一致している部分を
# 見つける、基礎的な問題ということになる。

def main():
    N, M = map(int, input().split())
    field_a = [input() for _ in range(N)]
    field_b = [input() for _ in range(M)]

    # 画像 A の(sx, sy) を左上として、画像 B と一致するかどうかを確認
    # for ～ else を用いた多重ループ脱出を用いている。
    # ……というか、実は他に for ～ else 使ってる人を見たことがない
    # 気もするので、せっかくだから詳しめにコメントを入れてみた。
    # よくわからない人は普通にフラッグで管理するのがオススメ。
    for sy in range(N-M+1):
        for sx in range(N-M+1):

            # (sx, sy) から各行を確認していく
            for dy in range(M):
                # 文字列をスライスして一致するかどうかを確認
                row_a = field_a[sy + dy][sx:sx+M]
                if field_b[dy] != row_a:
                    break

            # 全部一致したら、'Yes'にして終了 - (1)
            else:
                result = 'Yes'

                # この break は sx のループに対して働く
                break
        else:
            continue

        # 直前の else: continue のおかげで
        # ここには (1) で sx のループが break した後にしか来ない
        # これは、sy のループを break する
        break

    # 全探索が完了しても一致するところが無ければ 'No'
    else:
        result = 'No'

    print(result)

main()

abc054_b.py view raw

関連

コメントを残すコメントをキャンセル