AtCoder ABC 054 B - Template Matching (5Q, 緑色, 200 点)

少し実装が重たい全探索問題！

• 問題へのリンク

問題概要

の白黒グリッド と、 の白黒グリッド が与えられる ()。

グリッド のパターンがグリッド の中に含まれるかどうかを判定せよ。

制約

• 

考えたこと

グリッド のすべてのマス について、次の判定をしていけばよい。

---

グリッド の左上のマスを、グリッド のマス に配置したときに、 の各マスの色が の各マスの色に一致するかどうかを調べる

---

調べるべき のマス数は であり、さらにそれぞれについて の計算量で判定できる。

よって、全体の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> A(N), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    
    bool res = false;
    for (int i = 0; i+M-1 < N; i++) {
        for (int j = 0; j+M-1 < N; j++) {
            // A のマス (i, j) と B の左上のマスを重ねて一致するかを判定する
            bool ok = true;
            for (int i2 = 0; i2 < M; i2++) {
                for (int j2 = 0; j2 < M; j2++) {
                    if (A[i+i2][j+j2] != B[i2][j2]) ok = false;
                }
            }
            if (ok) res = true;
        }
    }
    cout << (res ? "Yes" : "No") << endl;
}