[Python] 行列 ABC218C

ABC218C

S と T に含まれる # の個数が異なる場合、答えは明らかに No です。そうでない場合を考えます。

S に対して 90 度回転を何回行うか 4 通りを全探索します。回転操作を施したあとのものを改めて S と呼ぶと、平行移動で S と T を一致させられるかどうかを判定すればよいです。

両者が一致するためには、S の最も左上のマスと T の最も左上のマスが一致することが必要であり、そのようなマスを求めることで平行移動量は一意に決まるため、平行移動により実際に一致するか判定すれば十分です。

以上により $O(N^2)$ で求めることができました。

サンプルコード

def rot(S):
    return list(zip(*S[::-1]))

def find_left_top(S):
    for i in range(N):
        for j in range(N):
            if S[i][j]=='#':
                return i,j

def is_same(S,T):
    Si,Sj = find_left_top(S)
    Ti,Tj = find_left_top(T)
    offset_i = Ti-Si
    offset_j = Tj-Sj
    for i in range(N):
        for j in range(N):
            ii = i+offset_i
            jj = j+offset_j
            if 0<=ii<N and 0<=jj<N:
                if S[i][j]!=T[ii][jj]: return False
            else:
                if S[i][j]=='#': return False
    return True

N = int(input())
S = [input() for _ in range(N)]
T = [input() for _ in range(N)]

cntS = sum(1 for i in range(N) for j in range(N) if S[i][j]=='#')
cntT = sum(1 for i in range(N) for j in range(N) if T[i][j]=='#')

if cntS != cntT:
    print("No")
    exit()

for _ in range(4):
    if is_same(S,T):
        print("Yes")
        exit()
    S = rot(S)
print("No")

解法は相応の時間で思い付いたのだが、実装が難しかった。
配列での行列回転処理が未熟なのが原因である。