C - Ideal Sheet Editorial by evima

Another Solution

A possible approach is to represent a sheet as a set of the black squares’ coordinates. In this case, a normalize function (as in the code below), which returns the given point set translated so that the smallest \(x\)-and \(y\)-coordinates are both \(0\), will be helpful. If you apply this to the given sheets \(A\), \(B\), \(X\), and normalizing the union of \(A\) and \(B\) translated in some way results in \(X\), the answer is Yes.

Sample Implementation (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: