官方题解｜使两方格相等的最少操作次数

题目解析

方格 $A$ 的状态可以用 $(P, Q)$ 来表示，其中 $P = (P_1, P_2, \ldots, P_H)$ 是代表 行 原始位置的排列，而 $Q = (Q_1,Q_2, \ldots, Q_W)$ 是代表 列 原始位置的排列。

一开始 $P = (1, 2, \ldots, H), Q = (1, 2, \ldots, W)$；交换相邻的行或列相当于交换 $P$ 或 $Q$ 中相邻的两个元素。

另外，当前方格中 $(i, j)$ 上的整数可以从 $A$ 的初始状态的 $(i, j)$ 上的整数获得。

例如，对于题目中第一个样例转换的过程，状态 $(P, Q)$ 变化为

$$\begin{aligned} &P = (1, 2, 3, 4), Q = (1, 2, 3, 4, 5)\\ \rightarrow &P = (1, 2, 3, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 2, 3, 5, 4)\\\rightarrow &P = (1, 3, 2, 4), Q = (1, 3, 2, 5, 4).\\ \end{aligned}$$

$(P, Q)$ 的总数是 $P$ 的排列的数量和 $Q$ 的排列的数量的乘积即 $H!W! \leq 5!\times 5! = 14400$。

因此，我们对这 $H!W!$ 个 $(P, Q)$，即 $(1, 2, \ldots, H)$的排列 $P$ 和 $(1, 2, \ldots, W)$ 的排列 $Q$ 中的每一个，执行以下操作：

• 首先，根据当前的 $(P, Q)$ 和 $A$ 构造方格 $C$ 并判断和方格 $B$ 是否相等。
• 如果相等，求从初始状态到达当前 $(P, Q)$ 的最小操作次数。

如果没有任意一对 $(P, Q)$ 和 $A$ 构造出的方格 $C$ 与方格 $B$ 相同，那么就不可能使方格 $A$ 和方格 $B$ 相等，输出 $-1$。

从初始状态到达当前状态 $(P, Q)$ 所需的最小操作数是以下操作之和：

• 通过重复交换相邻元素从初始序列 $(1, 2, \ldots, H)$ 得到排列 $P$ 所需的最少操作次数；
• 通过重复交换相邻元素从初始序列 $(1, 2, \ldots, W)$ 得到排列 $Q$ 所需的最小操作次数；

从排列 $(1, 2, \ldots, N)$ 开始，通过重复交换相邻的两个元素得到所需的排列 $A = (A_1, A_2, \ldots, A_N)$ 所需的运算次数为排列 $A$ 中的 逆序对 的数量，即

• $1 \leq i \lt j \leq N$，$A_i \gt A_j$ 的 $(i, j)$ 的个数。

因此，从初始状态到 $(P, Q)$ 所需的操作次数就是 $P$ 的 逆序对 的数量与 $Q$ 的 逆序对 的数量之和。

AC代码

#include <bits/stdc++.h>
using namespace std;

int count(vector<int> &a) {
    int n = a.size(), res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) ++res;
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        vector<vector<int>> b(n, vector<int>(m));
        for (auto &row : a)
            for (auto &x : row) cin >> x;
        for (auto &row : b)
            for (auto &x : row) cin >> x;
        vector<int> row(n), col(m);
        iota(begin(row), end(row), 0);
        iota(begin(col), end(col), 0);
        int res = 100;
        do {
            do {
                vector<vector<int>> c(n, vector<int>(m));
                for (int i = 0; i < n; ++i)
                    for (int j = 0; j < m; ++j)
                        c[i][j] = a[row[i]][col[j]];
                if (c != b) continue;
                res = min(res, count(row) + count(col));
            } while (next_permutation(begin(col), end(col)));
        } while (next_permutation(begin(row), end(row)));
        cout << (res < 100 ? res : -1) << '\n';
    }
    return 0;
}

复杂度分析

枚举所有的 $(P, Q)$ 时间复杂度为 $O(H!W!)$；
构造方格 $C$ 并判断是否和 $B$ 相等的时间复杂度为 $O(HW)$；
求 $P$ 的逆序对数量时间复杂度为 $O(H^2)$；
求 $W$ 的逆序对数量时间复杂度为 $O(W^2)$；
因此总的时间复杂度为 $O(H!W! \times (HW + H^2 + W^2))$。

---