MENU

JzxxOJ3501 碎片

JzxxOJ3501

交换不会改变原行列元素集合,最终矩阵要求对称行列元素集合相同,枚举用哪一行。

#include<cstdio>
#include<algorithm>
using namespace std;
int Num, T, N, M, swaprow[20][20], swapcol[20][20], visrow[20], viscol[20], rownum[20], colnum[20], flag;
char s[20][20], temp[20], temq[20];
void col(int pos, int type) {
    if (!flag)return;
    if (!pos) {
        for (int i = 1; i <= N; ++i)for (int j = 1; j <= M; ++j)if (s[rownum[i]][colnum[j]] != s[rownum[N - i + 1]][colnum[M - j + 1]])return;
        puts("YES"), flag = 0;
        return;
    }
    if (type) {
        for (int i = 1; i <= M; ++i)viscol[i] = 1, colnum[pos] = i, col(pos - 1, 0), viscol[i] = 0;
        return;
    }
    for (int i = 1; i <= M; ++i) {
        if (viscol[i])continue;
        for (int j = i + 1; j <= M; ++j)if (!viscol[j] && swapcol[i][j])viscol[i] = viscol[j] = 1, colnum[pos] = i, colnum[M + 1 - pos] = j, col(pos - 1, 0), viscol[i] = viscol[j] = 0;
        return;
    }
}
void row(int pos, int type) {
    if (!flag)return;
    if (!pos) { col(M + 1 >> 1, M & 1); return; }
    if (type) {
        for (int i = 1; i <= N; ++i)visrow[i] = 1, rownum[pos] = i, row(pos - 1, 0), visrow[i] = 0;
        return;
    }
    for (int i = 1; i <= N; ++i) {
        if (visrow[i])continue;
        for (int j = i + 1; j <= N; ++j)if (!visrow[j] && swaprow[i][j])visrow[i] = visrow[j] = 1, rownum[pos] = i, rownum[N + 1 - pos] = j, row(pos - 1, 0), visrow[i] = visrow[j] = 0;
        return;
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("fragment.in", "r", stdin), freopen("fragment.out", "w", stdout);
#endif
    scanf("%d%d", &Num, &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i)scanf("%s", s[i] + 1);
        for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j) {
            for (int k = 1; k <= M; ++k)temp[k] = s[i][k], temq[k] = s[j][k];
            sort(temp + 1, temp + M + 1), sort(temq + 1, temq + M + 1);
            swaprow[i][j] = 1;
            for (int k = 1; k <= M; ++k)if (temp[k] != temq[k]) { swaprow[i][j] = 0; break; }
        }
        for (int i = 1; i <= M; ++i)for (int j = 1; j <= M; ++j) {
            for (int k = 1; k <= N; ++k)temp[k] = s[k][i], temq[k] = s[k][j];
            sort(temp + 1, temp + N + 1), sort(temq + 1, temq + N + 1);
            swapcol[i][j] = 1;
            for (int k = 1; k <= N; ++k)if (temp[k] != temq[k]) { swapcol[i][j] = 0; break; }
        }
        flag = 1, row(N + 1 >> 1, N & 1);
        if (flag)puts("NO");
    }
}
Leave a Comment

captcha
请输入验证码