C - Shapes Editorial by kusano
このような問題では、グリッドの状態を#
の位置の集合として持つと楽になることがあります。
平行移動は、各要素から値を足し引きするだけで良く、範囲外アクセスを気にする必要が無くなります。90度の回転は、各要素 \((x, y)\) を \((y, -x)\) に置き換えるだけです。一致の判定には言語の機能を利用することができて、要素数を \(n\) として、\(O(n\log n)\) や \(O(n)\) で実装されていることが期待できます。
実装例(Python):
N = int(input())
# グリッドを読み込んで#の位置の集合を返す
def read():
S = set()
for y in range(N):
l = input()
for x in range(N):
if l[x]=="#":
S.add((x, y))
return S
S = read()
T = read()
for _ in range(4):
# 最も左(複数あればそのうちで最も上)の#を(0, 0)の位置にする
mx, my = min(S)
S = set((x-mx, y-my) for x, y in S)
mx, my = min(T)
T = set((x-mx, y-my) for x, y in T)
if S==T:
print("Yes")
exit(0)
# Tを回転
T = set((y, -x) for x, y in T)
print("No")
posted:
last update: