不要部分を削った行列が一致するか判定する
行列の不要な部分を削除した上で,片方の行列を回転させてもう一方と一致するかを調べれば良い.numpyによる解法
ちょっとズルいがnumpyだと簡単にかける.'#'
を含むindexの範囲は,次の考え方ができる:python - Numpy trim_zeros in 2D or 3D - Stack Overflow- 反時計回りに行列を90度回転させるのは,
np.rot90()
が使える:NumPy配列ndarrayを回転するnp.rot90 | note.nkmk.me
import numpy as np N = int(input()) S = [list(input()) for _ in range(N)] T = [list(input()) for _ in range(N)] S = np.array(S) T = np.array(T) Sind = np.where(S == '#') S = S[Sind[0].min():Sind[0].max() + 1, Sind[1].min():Sind[1].max() + 1] Tind = np.where(T == '#') T = T[Tind[0].min():Tind[0].max() + 1, Tind[1].min():Tind[1].max() + 1] for _ in range(4): if np.array_equal(S, T): exit(print('Yes')) S = np.rot90(S) print('No')
numpyなし
次は,上と同じことをnumpyなしで簡単に実現していました.スゴイ!Submission #25755698 - AtCoder Beginner Contest 218
#の座標の集合で見る
なるほど,わかりやすい考え方です.座標の集合をset
で扱う.
90度回転は,各座標点を
\begin{aligned}
\begin{pmatrix}
0 & -1\\
1 & 0
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
-y \\
x
\end{pmatrix}
\end{aligned}
とすることで表現できる(-90度なら\begin{pmatrix}
0 & -1\\
1 & 0
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
-y \\
x
\end{pmatrix}
\end{aligned}
\begin{aligned}
\begin{pmatrix}
0 & 1\\
-1 & 0
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
y \\
-x
\end{pmatrix}
\end{aligned}
となる.どちらでもよい.)
\begin{pmatrix}
0 & 1\\
-1 & 0
\end{pmatrix}
\begin{pmatrix}
x \\
y
\end{pmatrix}
=
\begin{pmatrix}
y \\
-x
\end{pmatrix}
\end{aligned}