Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、9問目を解説していきたいと思います。
問題名 【B – Template Matching】
入力
N：Aの絵画の辺の長さ
M：Bの絵画の辺の長さ
考察
今回は、M <= N <= 50なので、
A絵画の縦(i)と横(j)、B絵画の縦(p)と横(q)について全探索することが可能です O(50^4)
POINT
上限が50までのときは、4回までならfor文をネストできる
なので、全探索します。
手順
1, A[i][j]にBの絵画の左上を揃える i,jの位置を決める
2, そこから、Bの絵画は、右にp,下にqの要素についてみる p,qについて探索
3, その際、Aの絵画もBが移動した分だけ見る場所をかえるから、A[i+p][j+q]の要素をみるコード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N,M = MI()
A = []
B = []
for i in range(N):
a = S()
A.append(a)
for j in range(M):
b = S()
B.append(b)
for i in range(N):
for j in range(N):
cnt = 0
for p in range(M):
for q in range(M):
if i+p >= N or j+q >= N:
break
if A[i+p][j+q] == B[p][q]:
cnt += 1
if cnt == M*M:
print("Yes")
exit()
print("No")まとめ
こーゆー全探索の問題は、具体的にイメージしないと解きづらいですが、イメージさえできてしまえば割と簡単なので素早く解けるようになりたいですね！！
コメント