526互联

AtCoder Beginner Contest 332 (D)

发布时间 2023-12-11 15:16:46作者: du463

题目链接

思路：

这就是一个二维的全排列问题

代码:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define LNF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pll pair<int,int>
void solve(void) {
    ll n, m;
    cin >> n >> m;
    std::vector<std::vector<ll>> x(n, std::vector<ll>(m));
    
    std::vector<std::vector<ll>> y(n, std::vector<ll>(m));
    
    for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> x[i][j];
    for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> y[i][j];

    ll ans = LNF;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i;
    }
    do {
        std::vector<int> b(m);
        for (int i = 0; i < m; i++)b[i] = i;
        do {
            bool ok = 1;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (y[i][j] != x[a[i]][b[j]])ok = 0;
                }
            }
            if (ok) {
                ll sum = 0;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < i; j++)if (a[j] > a[i])sum++;
                }
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < i; j++)if (b[j] > b[i])sum++;
                }
                ans = min(ans, sum);
            }
        } while (next_permutation(b.begin(), b.end()));
    } while (next_permutation(a.begin(), a.end()));
    if (ans == LNF)ans = -1;
    cout << ans;
}
int main() {
    IOS
    int t = 1;
    // cin>>t;
    while (t--)
        solve();
    return 0;
}