Official
B - Seek Grid Editorial
by
B - Seek Grid Editorial
by
sotanishy
この問題は,\(4\) 重の for ループによる全探索によって解くことができます.
まず,\(a,b\) を \(1,\dots,N-M+1\) の範囲で全探索します.\(a,b\) を固定したときに,それが条件を満たすかどうかをさらに \(2\) 重の for ループにより判定します. 具体的には,\(i,j\) を \(1,\dots,M\) の範囲で全探索し,\(S_{a+i-1,b+j-1} \neq T_{i,j}\) となる \(i,j\) が \(1\) つでも存在するかどうか判定します.そのような \(i,j\) が存在しなければ,その時点で見ている \(a,b\) が答えです.
実装例 (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)
実装例 (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:
