题目解析
方格 AAA 的状态可以用 (P,Q)(P, Q)(P,Q) 来表示，其中 P=(P1,P2,…,PH)P = (P_1, P_2, \ldots, P_H)P=(P1 ,P2 ,…,PH ) 是代表 行 原始位置的排列，而 Q=(Q1,Q2,…,QW)Q = (Q_1,Q_2, \ldots, Q_W)Q=(Q1 ,Q2 ,…,QW ) 是代表 列 原始位置的排列。
一开始 P=(1,2,…,H),Q=(1,2,…,W)P = (1, 2, \ldots, H), Q = (1, 2, \ldots, W)P=(1,2,…,H),Q=(1,2,…,W)；交换相邻的行或列相当于交换 PPP 或 QQQ 中相邻的两个元素。
另外，当前方格中 (i,j)(i, j)(i,j) 上的整数可以从 AAA 的初始状态的 (i,j)(i, j)(i,j) 上的整数获得。
例如，对于题目中第一个样例转换的过程，状态 (P,Q)(P, Q)(P,Q) 变化为
P=(1,2,3,4),Q=(1,2,3,4,5)→P=(1,2,3,4),Q=(1,2,3,5,4)→P=(1,3,2,4),Q=(1,2,3,5,4)→P=(1,3,2,4),Q=(1,3,2,5,4). \begin{aligned} &P = (1, 2, 3, 4), Q = (1, 2, 3, 4, 5)\\ \rightarrow &P = (1, 2, 3, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 2, 3, 5, 4)\\\rightarrow &P = (1, 3, 2, 4), Q
= (1, 3, 2, 5, 4).\\ \end{aligned} →→→ P=(1,2,3,4),Q=(1,2,3,4,5)P=(1,2,3,4),Q=(1,2,3,5,4)P=(1,3,2,4),Q=(1,2,3,5,4)P=(1,3,2,4),Q=(1,3,2,5,4).
(P,Q)(P, Q)(P,Q) 的总数是 PPP 的排列的数量和 QQQ 的排列的数量的乘积即 H!W!≤5!×5!=14400H!W! \leq 5!\times 5! = 14400H!W!≤5!×5!=14400。
因此，我们对这 H!W!H!W!H!W! 个 (P,Q)(P, Q)(P,Q)，即 (1,2,…,H)(1, 2, \ldots, H)(1,2,…,H)的排列 PPP 和 (1,2,…,W)(1, 2, \ldots, W)(1,2,…,W) 的排列 QQQ 中的每一个，执行以下操作：
* 首先，根据当前的 (P,Q)(P, Q)(P,Q) 和 AAA 构造方格 CCC 并判断和方格 BBB 是否相等。
* 如果相等，求从初始状态到达当前 (P,Q)(P, Q)(P,Q) 的最小操作次数。
如果没有任意一对 (P,Q)(P, Q)(P,Q) 和 AAA 构造出的方格 CCC 与方格 BBB 相同，那么就不可能使方格 AAA 和方格 BBB 相等，输出 −1-1−1。
从初始状态到达当前状态 (P,Q)(P, Q)(P,Q) 所需的最小操作数是以下操作之和：
* 通过重复交换相邻元素从初始序列 (1,2,…,H)(1, 2, \ldots, H)(1,2,…,H) 得到排列 PPP 所需的最少操作次数；
* 通过重复交换相邻元素从初始序列 (1,2,…,W)(1, 2, \ldots, W)(1,2,…,W) 得到排列 QQQ 所需的最小操作次数；
从排列 (1,2,…,N)(1, 2, \ldots, N)(1,2,…,N) 开始，通过重复交换相邻的两个元素得到所需的排列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)A=(A1 ,A2 ,…,AN ) 所需的运算次数为排列 AAA 中的 逆序对 的数量，即
* 1≤i<j≤N1 \leq i \lt j \leq N1≤i<j≤N，Ai>AjA_i \gt A_jAi >Aj 的 (i,j)(i, j)(i,j) 的个数。
因此，从初始状态到 (P,Q)(P, Q)(P,Q) 所需的操作次数就是 PPP 的 逆序对 的数量与 QQQ 的 逆序对 的数量之和。
AC代码
复杂度分析
枚举所有的 (P,Q)(P, Q)(P,Q) 时间复杂度为 O(H!W!)O(H!W!)O(H!W!)；
构造方格 CCC 并判断是否和 BBB 相等的时间复杂度为 O(HW)O(HW)O(HW)；
求 PPP 的逆序对数量时间复杂度为 O(H2)O(H^2)O(H2)；
求 WWW 的逆序对数量时间复杂度为 O(W2)O(W^2)O(W2)；
因此总的时间复杂度为 O(H!W!×(HW+H2+W2))O(H!W! \times (HW + H^2 + W^2))O(H!W!×(HW+H2+W2))。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
