题解 [ABC332D] Swapping Puzzle
cjh20090318
·
·
题解
这题可能是 ABC 的 D 题里面难度的中等偏上，感觉确实和其他的 D 题相比有点难以实现。
题意
给两个 H \times W 的矩阵 A 和 B。
你可以对 A 矩阵交换相邻两行或相邻两列若干次。
输出 A 变换为 B 的最小操作次数，如果不能则输出 -1。
分析
根据[冒泡排序](https://oi-wiki.org/basic/bubble-sort/)我们可以知道交换相邻两个数可以做到这个数列的任何一个全排列，而这样的一个操作代价就是这个序列的逆序对数量。
所以我们直接枚举行的全排列和列的全排列即可（枚举全排列可以使用 [`std::next_permutation`](https://zh.cppreference.com/w/cpp/algorithm/next_permutation) 实现）。
时间复杂度 $O(H!W!)$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
int a[10][10],b[10][10];
int c[10][10];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)for(int j=0;j<m;j++) scanf("%d",&a[i][j]),c[i][j]=a[i][j];
for(int i=0;i<n;i++)for(int j=0;j<m;j++) scanf("%d",&b[i][j]);
int ans=-1;
vector<int> v(n);//枚举行的全排列。
for(int i=0;i<n;i++) v[i]=i;
do{
int now=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
c[v[i]][j]=a[i][j];
}
for(int i=0;i<n;i++)for(int j=i-1;j>=0;j--)now+=v[j]>v[i];//计算行的逆序对。
vector<int> w(m);//枚举列的全排列。
for(int i=0;i<m;i++) w[i]=i;
int tmp=-1;
do{
bool sol=1;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(c[i][w[j]]!=b[i][j]){sol=0;break;}//判断操作后相等。
if(sol){
int ts=0;
for(int i=0;i<m;i++)for(int j=i-1;j>=0;j--)ts+=w[j]>w[i];//计算列的逆序对。
if(~tmp) tmp=min(tmp,ts);
else tmp=ts;
}
}while(next_permutation(w.begin(),w.end()));
if(~tmp){
if(~ans) ans=min(ans,now+tmp);
else ans=now+tmp;
}
}while(next_permutation(v.begin(),v.end()));
printf("%d\n",ans);
return 0;
}
```