ゴリは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')