D - Flip and Rotate

2 secs 1024 MB

kusirakusira

問題

提出

テストケース

解説

$S$ に操作を施したときにありうる全ての盤面が $T$ と一致するか確認します。一見、

左右反転させたかどうか
上下反転させたかどうか
何度回転させたか
転置したかどうか

の $32$ 通りの盤面があると思えますが、実はありうる盤面はそれほど多くないです。

【操作について】

上下反転して右に $180$ 度回転させることで、左右反転と同じことが出来ます。
上下反転して右に $90$ 度回転させることで、転置と同じことが出来ます。

【盤面の種類数について】
実は $8$ 種類の盤面を考えればよいです。
図 (小)

上図より、作成できる盤面は開始点をどこにするか( $4$ 通り)×矢印をどの方向にするか( $2$ 通り)の $8$ 通りとなります。

よって、操作を上下反転・右に $90$ 度回転の $2$ つに絞ることが出来ます。(※)
元の盤面にこれらの操作を施した、 $8$ 通りの盤面について調べればよいことが分かります。

(※)
実際に上下反転と右に $90$ 度回転だけを行うことで、すべての盤面を作ることが出来ます。
余力のある方は試してみてください。

C++

xxxxxxxxxx
 
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
​
int main() {
    int N;
    cin >> N;
    vector<vector<int>> S(N, vector<int>(N));
    vector<vector<int>> T(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> S[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> T[i][j];
        }
    }
    vector<vector<int>> U(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            U[i][j] = S[i][N - 1 - j];
        }
    }
    vector<vector<int>> ss(N, vector<int>(N));
    vector<vector<int>> us(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            ss[i][j] = S[i][j];
            us[i][j] = U[i][j];
        }
    }
    bool pos = false;
    for (int k = 0; k < 4; k++) {
        vector<vector<int>> new_ss(N, vector<int>(N));
        vector<vector<int>> new_us(N, vector<int>(N));
        bool pos_sub_ss = true;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (ss[i][j] != T[i][j]) {
                    pos_sub_ss = false;
                }
            }
        }
        bool pos_sub_us = true;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (us[i][j] != T[i][j]) {
                    pos_sub_us = false;
                }
            }
        }
        if (pos_sub_ss || pos_sub_us) {
            pos = true;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                new_ss[i][j] = ss[j][N - 1 - i];
                new_us[i][j] = us[j][N - 1 - i];
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ss[i][j] = new_ss[i][j];
                us[i][j] = new_us[i][j];
            }
        }
    }
    if (pos) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Python

xxxxxxxxxx
 
def rotate_matrix(matrix, N):
    rotated = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            rotated[j][N - 1 - i] = matrix[i][j]
    return rotated
​
​
n = int(input())
S = []
T = []
for _ in range(n):
    s = list(map(int,input().split()))
    S.append(s)
for _ in range(n):
    t = list(map(int,input().split()))
    T.append(t)
​
for i in range(4):
    S = rotate_matrix(S, n)
    if(S==T):
        print("Yes")
        exit()
​
S = S[::-1]
for i in range(4):
    S = rotate_matrix(S, n)
    if(S==T):
        print("Yes")
        exit()
​
print("No")