算法
(模拟) $O(N^2)$
我们可以先把 $S$ 和 $T$ 的图像移动到左上角,然后枚举 $T$ 的 $4$ 种旋转,判断它是否和 $S$ 匹配。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using std::string;
int main() {
int n;
cin >> n;
vector<string> s(n), t(n);
rep(i, n) cin >> s[i];
rep(i, n) cin >> t[i];
auto rot = [&](vector<string> a) {
vector<string> res(n, string(n, '.'));
rep(i, n)rep(j, n) res[j][n - 1 - i] = a[i][j];
return res;
};
auto normalize = [&](vector<string> a) {
int li = n, lj = n;
rep(i, n)rep(j, n) if (a[i][j] == '#') {
li = min(li, i);
lj = min(lj, j);
}
vector<string> res(n, string(n, '.'));
rep(i, n)rep(j, n) if (a[i][j] == '#') {
res[i - li][j - lj] = '#';
}
return res;
};
auto same = [&](vector<string> a, vector<string> b) {
return normalize(a) == normalize(b);
};
rep(ri, 4) {
if (same(s, t)) {
puts("Yes");
return 0;
}
t = rot(t);
}
puts("No");
return 0;
}