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

深夜赤石。

题意解析：给定两个方格 $A,B$，每次可以进行以下的操作之一：

• 交换 $A$ 中相邻两行中的元素。
• 交换 $A$ 中相邻两列中的元素。

求最少操作次数使得 $A,B$ 相同。

注意到数据范围，$1\le n,m\le 5$。所以考虑爆搜。

我们枚举交换后的行、列的全排列，然后看看通过这种方式至少需要多少步。

显然步数为逆序对的个数。暴力求即可。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <vector>
using namespace std;
int a[6][6], b[6][6], c[6][6], d[6][6];
bool vis[6], vis2[6];
vector <int> v1 = {0}, v2 = {0};
int n, m;
int check(){
	memset(c, 0, sizeof(c));
	memset(d, 0, sizeof(d));
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			c[v1[j]][i] = a[j][i];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			d[i][v2[j]] = c[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(d[i][j] != b[i][j]) return 0x3f3f3f3f;
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			if(v1[i] > v1[j]) ans++;
		}
	}
	for(int i = 1; i <= m; i++){
		for(int j = i + 1; j <= m; j++){
			if(v2[i] > v2[j]) ans++;
		}
	}
	return ans;
}
int dfs2(int ct){
	if(ct > m) return check();
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= m; i++){
		if(!vis2[i]){
			vis2[i] = 1;
			v2.push_back(i);
			ans = min(ans, dfs2(ct + 1));
			v2.pop_back();
			vis2[i] = 0;
		}
	}
	return ans;
}
int dfs(int ct){
	if(ct > n) return dfs2(1);
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			vis[i] = 1;
			v1.push_back(i);
			ans = min(ans, dfs(ct + 1));
			v1.pop_back();
			vis[i] = 0;
		}
	}
	return ans;
}
void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> b[i][j];
		}
	}
	int ans = dfs(1);
	if(ans >= 0x3f3f3f3f) cout << "-1\n";
	else cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：$O(tn^2m^2nm)$
好猎奇的复杂度啊