グリッド A の現在の状態は、 現在 \(i\) 行目にある行が初期状態での何行目に当たるかを表す順列 \(P = (P_1, P_2, \ldots, P_H)\) と、 現在 \(j\) 列目にある列が初期状態での何列目に当たるかを表す順列 \(Q = (Q_1,Q_2, \ldots, Q_W)\) の組 \((P, Q)\) で表せます。

初期状態では、\(P = (1, 2, \ldots, H), Q = (1, 2, \ldots, W)\) であり、 隣接する行・列の入れ替え操作は、それぞれ \(P, Q\) 上の隣接する \(2\) つの要素の入れ替えに対応します。 また、\((P, Q)\) の情報から、現在のグリッドのマス \((i, j)\) に書かれた整数は、初期状態のグリッドでマス \((P_i, Q_j)\) に書かれていた整数だと解ります。

例えば、入出力例１の説明文では、

\[ \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, Q)\) が変化します。

グリッドの全状態数は、\(P\) としてあり得る \((1, 2, \ldots, H)\) の順列 \(H!\) 通り、\(Q\) としてあり得る \((1, 2, \ldots, W)\) の順列 \(W!\) 通りの組の総数 \(H!W! \leq 5!\times 5! = 14400\) と、 十分小さいのでそれらを全探索することで実行制限時間内に本問題の答えを得ることができます。

つまり、\((1, 2, \ldots, H)\) の順列 \(P\) と、\((1, 2, \ldots, W)\) の順列 \(Q\) の組 \((P, Q)\) としてあり得るもの \(H!W!\) 通りそれぞれについて、下記の処理を行います。

• まず、今調べている \((P, Q)\) において、グリッド A がグリッド B と一致しているか判定する。
• もし一致しているなら、初期状態からその \((P, Q)\) に到達するための最小操作回数を計算する。

そして、上で計算した最小操作回数の中の最小値を出力すれば良いです。 ただし、グリッド A がグリッド B と一致するような状態 \((P, Q)\) が一つもなかった場合は、グリッド A とグリッド B を一致させることはできないので、-1 を出力します。

また、今調べている \((P, Q)\) に、初期状態から到達するための最小操作回数は、

• 初期状態の数列 \((1, 2, \ldots, H)\) を、隣接する \(2\) 項を入れ替える操作を繰り返して所望の順列 \(P\) に作り替えるための最小操作回数と、
• 初期状態の数列 \((1, 2, \ldots, W)\) に、隣接する \(2\) 項を入れ替える操作を繰り返して所望の順列 \(Q\) に作り替えるための最小操作回数

の和ですが、 一般に、数列 \((1, 2, \ldots, N)\) を、隣接する \(2\) 項 を入れ替える操作を繰り返して所望の順列 \(A = (A_1, A_2, \ldots, A_N)\) に作り替えるための最小操作回数は、 順列 \(A\) の転倒数、つまり、

\(1 \leq i \lt j \leq N\) かつ \(A_i \gt A_j\) を満たす組 \((i, j)\) の個数

として与えられるので、 初期状態から状態 \((P, Q)\) に到達するための最小操作回数を求めるには、\(P\) の転倒数と \(Q\) の転倒数の和を求めれば良いです。

また別解として、上で用いた状態 \((P, Q)\) や、グリッド A そのものの情報（ \(HW\) 個の整数の並び）をキーとして幅優先探索( BFS )を行う方法でも、本問題に正解することができます。

以下に、C++言語による本問題の正解例（順列全探索による解法）を記載します。

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1000000000;

int main(void)
{
  int h, w, a[6][6], b[6][6];
  cin >> h >> w;
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> a[i][j];
  for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) cin >> b[i][j];
  
  int p[6], q[6];
  for(int i = 1; i <= h; i++) p[i] = i;
  for(int i = 1; i <= w; i++) q[i] = i;
  
  int ans = inf;
  do{
    do{
      
      bool match = true;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++){
        if(a[p[i]][q[j]] != b[i][j]) match = false;
      }
      if(!match) continue;
      
      int pinv = 0, qinv = 0;
      for(int i = 1; i <= h; i++) for(int j = 1; j <= h; j++) if(i < j && p[i] > p[j]) pinv++;
      for(int i = 1; i <= w; i++) for(int j = 1; j <= w; j++) if(i < j && q[i] > q[j]) qinv++;
      ans = min(ans, pinv+qinv);
      
    }while(next_permutation(q+1, q+w+1));
  }while(next_permutation(p+1, p+h+1));
  
  if(ans == inf) cout << -1 << endl;
  else cout << ans << endl;
  
  return 0;
}