D - Swapping Puzzle (交换i和i+1行或者i和i+1列使得a矩阵和b矩阵相同,用next_permutation函数和逆序对)

题目:https://atcoder.jp/contests/abc332/tasks/abc332_d

思想:首先交换行对列中的元素无影响,同理交换列对行的元素无影响。

我们用暴力枚举(两层next_premutation函数)来找到所有的排列方式,同时判断这种排列方式是否a矩阵与b矩阵相同,初始行数组和列数组是1-n,1-m,全排列之后,如果相同,用逆序对同时记录行变化了多少以及列变化了多少,并且不断更新最小的交换次数。

代码:

// Problem: D - Swapping Puzzle
// Contest: AtCoder - AtCoder Beginner Contest 332
// URL: https://atcoder.jp/contests/abc332/tasks/abc332_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

typedef long long ll;

const int N = 10;
const int inf = 0x3f3f3f3f;

int n,m;
int a[N][N],b[N][N];
int row[N],col[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	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];
		}
	}
	
	for(int i=1;i<=n;i++){
		row[i]=i;
	}
	for(int i=1;i<=m;i++){
		col[i]=i;
	}
	int res=inf;
	do{
		do{
			int flag=1;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(a[row[i]][col[j]]!=b[i][j]){  //判断是否相同
						flag=0;
					}
				}
			}
			if(flag){
				int ans=0;
				for(int i=1;i<=n;i++){
					for(int j=i+1;j<=n;j++){
						if(row[i]>row[j]){
							ans++;
						}
					}
				}
				for(int i=1;i<=m;i++){
					for(int j=i+1;j<=m;j++){
						if(col[i]>col[j]){
							ans++;
						}
					}
				}
				res=min(res,ans);
			}
		}while(next_permutation(row+1,row+n+1));
	}while(next_permutation(col+1,col+m+1));
	
	if(res==inf) res=-1;
	cout<<res<<"\n";
	
	
	return 0;	

}