AtCoder Beginner Contest 332 D题 Swapping Puzzle

标签：全排列、深度优先搜索
题意：给定两个行数和列数分别是$H$和$W$的二维矩阵$A$和$B$。可以对$A$矩阵的相邻两行或者相邻两列进行交换，求最少的交换次数能够使得$A$矩阵变成$B$矩阵。（$2<=H,W<=5$）
题解：看到这个数据这么小，很容易想到暴搜。对矩阵$A$的行和列分别做一个全排列深搜。
举个例子，比如行数$H=3$，列数$W=3$。
那么一开始行的情况：$1、2、3$
来看个行的其中一个全排列的情况：$2、3、1$，这个情况也就是说现在的第$1$行是原来的第$2$行，现在的第$2$行是原来的第$3$行，现在的第$3$行是原来的第$1$行。

那我们是不是弄出了一种行的交换情况，那这种情况行到底交换了多少次呢？熟悉逆序数的同学，应该能发现交换的次数 其实就是这个情况的序列逆序数的值。
比如这里$2、3、1$，$2$要在$1$的前面 肯定是和$1$进行了交换。

同理，列也是类似的；我们对行和列都做一个全排列操作之后，分别统计一下对应序列的逆序数值，相加一下就是改变成目前这种情况，总的交换次数。

然后还有个问题就是如何去判断这种情况下$A$矩阵和$B$矩阵是否相同的，我们可以把全排列的情况记录一下，到时候比较的时候看看这种情况下$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;
}