C - Ideal Sheet Editorial by evima

別解

シートを黒いマスの座標の集合として表す方針が考えられます。この場合、点集合を与えると最小の \(x\) 座標と最小の \(y\) 座標がともに \(0\) となるように平行移動して返す関数(下記コードの normalize)が役立ちます。入力で与えられたシート \(A, B, X\) にこれを適用し、\(A\) と適当に平行移動した \(B\) の和集合を normalize した結果が \(X\) と一致することがあれば答えは Yes です。

実装例 (Python)

def convert(H, W, S):
    s = set()
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                s.add((i, j))
    return s

def normalize(s):
    my = min(y for (y, x) in s)
    mx = min(x for (y, x) in s)
    return set((y - my, x - mx) for (y, x) in s)

HA, WA = map(int, input().split())
A = normalize(convert(HA, WA, [input() for _ in range(HA)]))
HB, WB = map(int, input().split())
B = normalize(convert(HB, WB, [input() for _ in range(HB)]))
HX, WX = map(int, input().split())
X = normalize(convert(HX, WX, [input() for _ in range(HX)]))
ans = False
for dy in range(-HX, HX):
    for dx in range(-WX, WX):
        ans |= normalize(A.union((y + dy, x + dx) for (y, x) in B)) == X
print('Yes' if ans else 'No')

posted:
last update: