If \(S\) and \(T\) have different number of #s, then the answer is obviously No. We consider the other cases.

We brute force through all \(4\) possibility of \(90\)-degree rotation of \(S\). If we newly denote by \(S\) the shape after the rotation is applied, then we want to determine if \(S\) and \(T\) can be matched by translations.

In order to match them, the leftmost and uppermost square of \(S\) and the leftmost and uppermost square of \(T\) should match. Once we have such squares, we can uniquely determine how much we should translate the squares, so it is sufficient to check if the translation actually matches them.

Therefore, we could solve it in a total of \(O(N^2)\) time.

Sample code (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")

Note that we may search exhaustively over all possible number of rotations and amount of translations, checking for the correspondence of each square of \(S\) and each square of \(T\), which is naively an \(O(N^4)\)-solution but can be improved to \(O(N^3)\) by aborting comparison once it detects a mismatch, so that it fits in the time limit.

Note that we may search exhaustively over all possible number of rotations and amount of translations, checking for the correspondence of each square of \(S\) and each square of \(T\), which is naively an \(O(N^4)\)-solution but can be improved by aborting comparison once it detects a mismatch and randomizing the comparison order, so that it fits in the time limit.

Sample code (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()

# shuffle
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  # <--Important
			if flag:
				print("Yes")
				exit()
	# rot
	S_list = [(y,N-1-x) for x,y in S_list]
print("No")