AtCoder-ABC218 C - Shapes【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest218のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 218 - AtCoder

AtCoder Beginner Contest218 C - Shapes

C - Shapes

問題文

2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。

S は N 行 N 列のグリッド内にあり、S i,j が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T i,j が # であるようなマス全体からなります。

S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。

制約

・1≤N≤200
・S,T は # と . のみからなる
・S,T は 1 つ以上 # を含む

解答例

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


def shift(x):
    for i in range(n):
        for j in range(n):
            if x[i][j] == "#":
                return i,j


def judge(x,y):
    xi, xj = shift(x)
    yi, yj = shift(y)
    offset_i = yi - xi
    offset_j = yj - xj
    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 x[i][j] != y[ii][jj]:
                    return False
            else:
                if x[i][j] == "#":
                    return False
    return True


n = int(input())

S = []
for _ in range(n):
    S.append(input())

T = []
for _ in range(n):
    T.append(input())

cntS = 0
for i in range(n):
    for j in range(n):
        if S[i][j] == "#":
            cntS += 1

cntT = 0
for i in range(n):
    for j in range(n):
        if T[i][j] =="#":
            cntT += 1

flag = False

if cntS == cntT:
    for _ in range(4):
        if judge(S,T):
            flag = True
        S = rot(S)

if flag:
    print("Yes")
else:
    print("No")