D题：Swapping Puzzle
标签：全排列、深度优先搜索
题意：给定两个行数和列数分别是
H
H
H和
W
W
W的二维矩阵
A
A
A和
B
B
B。可以对
A
A
A矩阵的相邻两行或者相邻两列进行交换，求最少的交换次数能够使得
A
A
A矩阵变成
B
B
B矩阵。（
2
<
=
H
,
W
<
=
5
2<=H,W<=5
2<=H,W<=5）
题解：看到这个数据这么小，很容易想到暴搜。对矩阵
A
A
A的行和列分别做一个全排列深搜。
举个例子，比如行数
H
=
3
H=3
H=3，列数
W
=
3
W=3
W=3。
那么一开始行的情况：
1
、
2
、
3
1、2、3
1、2、3
来看个行的其中一个全排列的情况：
2
、
3
、
1
2、3、1
2、3、1，这个情况也就是说现在的第
1
1
1行是原来的第
2
2
2行，现在的第
2
2
2行是原来的第
3
3
3行，现在的第
3
3
3行是原来的第
1
1
1行。
那我们是不是弄出了一种行的交换情况，那这种情况行到底交换了多少次呢？熟悉逆序数的同学，应该能发现交换的次数 其实就是这个情况的序列逆序数的值。
比如这里
2
、
3
、
1
2、3、1
2、3、1，
2
2
2要在
1
1
1的前面 肯定是和
1
1
1进行了交换。
同理，列也是类似的；我们对行和列都做一个全排列操作之后，分别统计一下对应序列的逆序数值，相加一下就是改变成目前这种情况，总的交换次数。
然后还有个问题就是如何去判断这种情况下
A
A
A矩阵和
B
B
B矩阵是否相同的，我们可以把全排列的情况记录一下，到时候比较的时候看看这种情况下
A
A
A矩阵的当前行和当前列是对应初始
A
A
A矩阵的哪一行和哪一列，然后对应进行比较即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 1e9;
int a[15][15], b[15][15];
int c[15], d[15], vis1[15], vis2[15];
void dfs1(int p) { // 做列的全排列
if (p == m + 1) {
bool f = true;
for (int i = 1; i <= n; i++) {
if (!f) break;
for (int j = 1; j <= m; j++) {
if (a[c[i]][d[j]] != b[i][j]) {
f = false;
break;
}
}
}
if (f) {
int cnt = 0; // 操作次数
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (c[i] > c[j]) cnt++;
for (int i = 1; i <= m; i++)
for (int j = i + 1; j <= m; j++)
if (d[i] > d[j]) cnt++;
ans = min(ans, cnt);
}
return ;
}
for (int i = 1; i <= m; i++) {
if (!vis2[i]) {
vis2[i] = 1;
d[p] = i;
dfs1(p + 1);
vis2[i] = 0;
}
}
}
void dfs2(int p) { // 针对行做一个全排列
if (p == n + 1) {
dfs1(1);
return ;
}
for (int i = 1; i <= n; i++) {
if (!vis1[i]) {
vis1[i] = 1;
c[p] = i; // 现在的第p行是原来的第i行
dfs2(p + 1);
vis1[i] = 0;
}
}
}
int main() {
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];
dfs2(1);
if (ans == 1e9) ans = -1;
cout << ans;
return 0;
}
