XVI Open Cup named after E.V. Pankratiev. GP of SPB

G.给你一个由1～16组成的$4 imes 4$的棋盘，你每次可以交换任意两个位置，或者交换任意两行，或者交换任意两列。

注意到对于任意一种方案，我们都可以找到一个方案使得先换行，再换列，最后两两交换，所以一开始枚举行的排列和列的排列，然后模拟。两两交换的过程实际是将一个置换变为恒等变换的过程。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
typedef long long LL;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<P> VII;
int a[6][6], b[6][6];
struct node {
    int op, x, y;
    node(int _op = 0, int _x = 0, int _y = 0): op(_op), x(_x), y(_y) {}
};
int main() {
    rep(i, 1, 4) rep(j, 1, 4) scanf("%d", &a[i][j]);
    int p[6], q[6], r[6], c[6];
    auto calc = [&](int x, int y) -> int {
        return (x - 1) * 4 + y;
    };
    vector<node> ansv;
    int ans = 100;
    auto solve = [&]() {
        vector<node> v;
        rep(i, 1, 4) rep(j, 1, 4) b[i][j] = a[i][j];
        rep(i, 1, 4) r[i] = p[i], c[i] = q[i];
        rep(i, 1, 4) {
            if (r[i] != i) {
                int t;
                rep(j, 1, 4) {
                    if (r[j] == i) {
                        t = j;
                        break;
                    }
                }
                swap(r[i], r[t]);
                v.push_back(node(0, i, t));
                rep(j, 1, 4) swap(b[i][j], b[t][j]);
            }
        }
        rep(i, 1, 4) {
            if (c[i] != i) {
                int t;
                rep(j, 1, 4) {
                    if (c[j] == i) {
                        t = j;
                        break;
                    }
                }
                 swap(c[i], c[t]);
                 v.push_back(node(1, i, t));
                 rep(j, 1, 4) swap(b[j][i], b[j][t]);
            }
        }
        rep(i, 1, 4) rep(j, 1, 4) {
            int c = calc(i, j);
            if (b[i][j] != c) {
                int rr = -1, cc = -1;
                rep(k, 1, 4) {
                    rep(l, 1, 4) {
                        if (b[k][l] == c) {
                            rr = k; 
                            cc = l;
                            break;
                        }
                    }
                    if (rr != -1) break;
                }
                swap(b[i][j], b[rr][cc]);
                v.push_back(node(2, calc(i, j), calc(rr, cc)));
            }
        }
        if (v.size() < ans) {
            ansv = v;
            ans = v.size();
        }
    };
    rep(i, 1, 4) p[i] = i;
    do {
        rep(i, 1, 4) q[i] = i;
        do {    
            solve();
        } while (next_permutation(q + 1, q + 5));
    } while (next_permutation(p + 1, p + 5)); 
    printf("%d
", ans);
    for (node &x: ansv) {
        if (x.op == 0) {
            printf("%c-%c
", char('a' + x.x - 1), char('a' + x.y - 1));
        }
        if (x.op == 1) {
            printf("%d-%d
", x.x, x.y);
        }
        if (x.op == 2) {
            printf("%c%d-%c%d
", char('a' + (x.x - 1) / 4), (x.x - 1) % 4 + 1, char('a' + (x.y - 1) / 4), (x.y - 1) % 4 + 1);
        }
    }

}
/*
09 11 05 12
10 07 06 08
01 03 02 04
13 16 14 15
*/