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

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

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

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

実装例(Python)

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")

なお、回転回数と平行移動量を全探索し、\(S\) の各マスと \(T\) の各マスの対応を確かめるような愚直な \(O(N^4)\) の解法も、\(S\) の # のマスをリストなどで持ち、一致しないことがわかった時点で比較を打ち切ることで、\(O(N^3)\) に改善することができるため、実行時間制限に間に合わせることができます。

なお、回転回数と平行移動量を全探索し、\(S\) の各マスと \(T\) の各マスの対応を確かめるような愚直な \(O(N^4)\) の解法も、\(S\) の # のマスをリストなどで持ちシャッフルし、一致しないことがわかった時点で比較を打ち切ることで、十分高速に動作します。（expected \(O(N^2)\) に見えますが未証明です）

実装例(Python)

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

S_list = list((i,j) 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 len(S_list)!=cntT :
	print("No")
	exit()

# シャッフル
random.shuffle(S_list)

for _ in range(4):
	for i in range(-N+1,N):
		for j in range(-N+1,N):
			flag=True
			for x,y in S_list:
				if not (0<=x+i<N and 0<=y+j<N and T[x+i][y+j]=='#'):
					flag=False
					break  # <--重要
			if flag:
				print("Yes")
				exit()
	# rot
	S_list = [(y,N-1-x) for x,y in S_list]
print("No")