把两个dfs连起来
package AtCoder.begin332;
import javax.swing.plaf.nimbus.State;
import java.util.*;
public class D {
/**
* 思路比较简单 :
* 因为交换相邻的行和相邻的列其实就等同于随意交换 -> 可以自己试一试
* dfs枚举行和列的全排列, 然后判断每一个状态的 a 是否和 b 相同
* 相同了如何更新答案 -> 这个状态的交换次数就是行排列和列排列的逆序数之和
*
* 实现过程被edu了 :
* 不必真的取交换, 直接记录行号和列号, 然后到时候根据行号和列号去原数据查就好了
* 因为交换行和交换列是互不影响的
*
* 总结 :
* dfs还是需要多练习一下, 光有思路无法实现是最难受的
* */
static int[][] a, b;
static int[] ri, wi;
static int n, m, ans = Integer.MAX_VALUE;
static Set<Integer> sr = new HashSet<>();
static Set<Integer> sw = new HashSet<>();
private static void init() {
a = new int[n + 10][m + 10];
b = new int[n + 10][m + 10];
ri = new int[n + 10]; // 记录行当前的排列
wi = new int[m + 10]; // 记录列当前的排列
}
private static void dfs_row(int u) { // 枚举行的全排列
if (u > n) dfs_col(1);
for (int i = 1; i <= n; i ++ ) {
if (sr.contains(i)) continue;
ri[u] = i;
sr.add(i);
dfs_row(u + 1);
sr.remove(i);
}
}
private static void dfs_col(int u) { // 枚举列的全排列
if (u > m) {
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[ri[i]][wi[j]] != b[i][j]) return ; // 不符合要求
// 算出这个状态的答案
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
if (ri[i] > ri[j]) res ++ ;
for (int i = 1; i <= m; i ++ )
for (int j = i + 1; j <= m; j ++ )
if (wi[i] > wi[j]) res ++ ;
ans = Math.min(ans, res); // 尝试更新答案
return ;
}
for (int i = 1; i <= m; i ++ ) {
if (sw.contains(i)) continue;
wi[u] = i;
sw.add(i);
dfs_col(u + 1);
sw.remove(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt();
init();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
a[i][j] = sc.nextInt();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
b[i][j] = sc.nextInt();
dfs_row(1);
if (ans == Integer.MAX_VALUE) System.out.println(-1); // 无解
else System.out.println(ans);
}
}