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: