题意简述

给定一个 $n \times m$ 的排列矩阵 $a$（元素为 $1 \sim n\cdot m$ 的排列），需要构造另一个排列矩阵 $b$，使得每个位置上的数都与 $a$ 中对应位置的数不同。若无法构造输出 $-1$。

解法

• 若 $n \cdot m = 1$，此时只有一个数，无论如何排列都会与原矩阵相同，输出 $-1$。
• 若 $n \cdot m > 1$，可以将每个数循环加 1（模 $n\cdot m$），即 $b_{i,j} = (a_{i,j} \bmod (n\cdot m)) + 1$。
  • 这样，所有数都会变成原来的下一个数（$n\cdot m$ 变成 $1$）。因为 $n\cdot m \ge 2$，对于任意位置，新数都不等于原数。
  • 同时，新矩阵仍然是一个排列，包含了 $1$ 到 $n\cdot m$ 的所有整数。
• 直接按原位置输出新数即可。

复杂度

• 每组测试数据需要遍历整个矩阵一次，时间复杂度 $O(n \cdot m)$。
• 总计算量不超过 $5\times 10^4$，完全可以接受。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int total = n * m;
        if (total == 1) {
            int x;
            cin >> x;
            cout << "-1\n";
            continue;
        }
        vector<vector<int>> a(n, vector<int>(m));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> a[i][j];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int val = a[i][j] % total + 1;
                cout << val << " \n"[j == m - 1];
            }
        }
    }
    return 0;
}