Official

D - Seek Grid Editorial by en_translator


This problem can be solved by exhaustive search with a quadruple for loop.

First, search \(a\) and \(b\) within the range \(1,\dots,N-M+1\). For fixed \(a\) and \(b\), use additional double for loop to check if it satisfies the condition. Specifically, enumerate \(i\) and \(j\) within the range \(1,\dots,M\) to check any \((i,j)\) satisfies \(S_{a+i-1,b+j-1} \neq T_{i,j}\). If none of them does, the current \((a,b)\) is the answer.

Sample code (Python)

N, M = map(int, input().split())
S = [input() for _ in range(N)]
T = [input() for _ in range(M)]
for a in range(N - M + 1):
    for b in range(N - M + 1):
        ok = True
        for i in range(M):
            for j in range(M):
                if S[a + i][b + j] != T[i][j]:
                    ok = False
        if ok:
            print(a + 1, b + 1)

Sample code (C++)

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N), T(M);
    for (auto& x : S) cin >> x;
    for (auto& x : T) cin >> x;

    for (int a = 0; a <= N - M; ++a) {
        for (int b = 0; b <= N - M; ++b) {
            bool ok = true;
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < M; ++j) {
                    if (S[a + i][b + j] != T[i][j]) {
                        ok = false;
                    }
                }
            }
            if (ok) {
                cout << a + 1 << " " << b + 1 << endl;
            }
        }
    }
}

posted:
last update: