ゴリはABC-Cが解けませんでした。ぐぬぬ
問題概要
グリッドAとグリッドBを平行移動して重ねた結果、黒いマスがグリッドXと一致させることができるか？
グリッドA,B,X の縦横の大きさは最大10。
最初考えた方針 (WA)
30*30 の領域を用意して、(10,10) が始点になるようにAを固定する。
Bの貼り付け場所として (0,0) ～ (20,20) を試す。
で、これのBの貼り付け場所 21 * 21 箇所それぞれについて、Xの始点も 21 * 21 箇所試すという方針を考えました。
Xの最大サイズは10なので、10離れた位置まで試しておけば大丈夫だろう、という考えでした。
激ヤバケースとは
コンテスト後にわかったのですが、たとえばこのようなケースが存在します。
Aの右下が1マスだけ塗られていて、Bの左上が1マスだけ塗られていて、Xは左上と右下が塗られているケースです。
このケースだと、Aの始点とBの始点は縦横最大18マス離れてしまい、最初の方針では調べきれてないので落ちてしまいます
AC方針
50 * 50 の領域を用意して、(20,20) が始点になるようにAを固定する。
Bの貼り付け場所として (0,0) ～ (40,40) を試す。
これのBの貼り付け場所 41 * 41 箇所それぞれについて、Xの始点も 41 * 41 箇所試す
これに直したらいけました
ACコード (コンテスト後)
HA,WA = map(int,input().split())
A = [input() for _ in range(HA)]
HB,WB = map(int,input().split())
B = [input() for _ in range(HB)]
HX,WX = map(int,input().split())
X = [input() for _ in range(HX)]
c = sum(row.count('#') for row in X)
for si in range(41):
for sj in range(41):
Z = [['.']*50 for _ in range(50)]
for ai in range(HA):
for aj in range(WA):
if A[ai][aj]=='#':
Z[ai+20][aj+20] = '#'
for bi in range(HB):
for bj in range(WB):
if B[bi][bj]=='#':
Z[si+bi][sj+bj] = '#'
zc = sum(row.count('#') for row in Z)
if c != zc: continue
def exist(xi,xj):
for i in range(HX):
for j in range(WX):
if Z[xi+i][xj+j] != X[i][j]:
return False
return True
for xi in range(41):
for xj in range(41):
if exist(xi,xj):
exit(print('Yes'))
print('No')
