このような問題では、グリッドの状態を#の位置の集合として持つと楽になることがあります。

平行移動は、各要素から値を足し引きするだけで良く、範囲外アクセスを気にする必要が無くなります。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")