\(\mathbb{Z}\times \mathbb{Z}\) 平面における回転を実装すると， \(N \times N\) のグリッドの回転と違って index のはみ出しを気にしなくて良いので楽． グラフの様に，'#'の位置情報を持っておく．
\(vs_{i} := s_{i,j} = \) '#'となる \(j\) 全体
と定義する． \(t\) も同様．
後は， \(s,t\) がshiftで一致することを調べる． \(s,t\) それぞれに対して '#'の一番左上のマスを調べて，その座標が原点に来るように移動する．
回転は， \(\,(x,y)\) を \((y,-x)\) にすれば良い． これは，\(\mathbb{Z}\times \mathbb{Z}\) 平面における回転だから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
cinv(s);
cinv(t);
using T = map<ll, set<ll>>;
T v;
rep(i,n){
rep(j,n){
if(str[i][j] == '#') v[i].insert(j);
}
}
return v;
};
auto mini = [&](const T &v) -> pll {
for(auto [i,vec]:v){
for(auto j:vec){
return {i,j};
}
}
return {INFL, INFL};
};
auto move = [&](T &v, ll x, ll y) -> void {
T tmp;
for(auto [i,vec]: v){
for(auto j: vec){
tmp[i-x].insert(j-y);
}
}
swap(tmp, v);
};
auto rot = [&](T &v) -> void {
T tmp;
for(auto [i,vec]: v){
for(auto j: vec){
tmp[j].insert(-i);
}
}
swap(tmp, v);
};
T mps = read(s);
T mpt = read(t);
rep(_,4){
{
auto [mx, my] = mini(mps);
move(mps, mx, my);
}
{
auto [mx, my] = mini(mpt);
move(mpt, mx, my);
}
if(mps == mpt){
cout << "Yes" << endl;
return 0;
}
rot(mpt);
}
cout << "No" << endl;
return 0;
}
