この問題は半分全列挙によって解くことができます。

まず、\(20\) 回以下の操作で目標とするマス目を作る事ができるか判定する方法について考えます。

\(1\) 回の操作で行うことのできる操作は \(4\) 種類しかないことから、あるマス目の状態から \(K\) 回以下の操作で作る事ができる状態は高々 \(4^K\) 個です。さらに、同じ場所に対する回転操作を連続で行うと元に戻ることに注意すると、高々 \(4\cdot 3^{K-1}\) 個である事がわかります。しかし、今回の制約の下で作ることのできる状態は最大で \(4\cdot 3^{19}\) \((\simeq 5\cdot 10^9)\) 個となり、列挙は現実的ではありません。

ここで、操作が \(180\) 度回転であることから、逆操作がその操作自身であることに注目すると、\(K\) 回以下の操作で目標とするマス目を作る事ができる状態の集合は、目標とする状態から \(K\) 回以下の操作で作ることのできる状態の集合と一致します。
よって、最初の状態と目標としている最終状態からそれぞれ \(10\) 手以内で作ることのできる状態の集合 \(T\), \(U\) を考えたとき、\(T\) と \(U\) が共通部分を持つ、すなわち最初のマス目の状態および最終状態のどちらからも \(10\) 手以内に作ることのできる状態が存在すれば、その状態を経由して \(20\) 回以下の操作で最終状態を作る事ができ、逆に持たなければ不可能であるという事ができます。

さて、最小の操作回数を求める方法についてですが、これも先ほどの\(T,U\) を分割する事で同様にして解く事ができます。 \(i=0,1,\ldots,10\) について、\(T_i\) を最初の状態から \((i-1)\) 回以下の操作では作れないが \(i\) 回の操作で作ることのできる状態の集合として定義します。(ここで、\(T_0\) は初期状態のみからなる集合です。) 同様に \(U_i\) \((0\leq i\leq 10)\) も最終状態から \(i\) 回の操作で初めて作ることのできる集合として定義すると、答えは、 \(T_i\) と \(U_j\) が共通部分を持つような \((i,j)\) における \((i+j)\) の最小値となります。

実際には、\(T_i\)と \(U_j\) が共通部分を持つとき、定義から \(i+j=i'+j'\) であるような \(T_{i'}\) と \(U_{j'}\) も共通部分を持つことから、各 \(i+j\) の値に対して \(1\) つの組み合わせを確かめれば十分であり、例えば次の \(2\) つを確かめれば十分です。

• \(i=0,1,\ldots,10\) について、\(T_i\) と \(U_0\) が共通部分を持つか
• \(j=1,2,\ldots, 10\) について、\(T_{10}\) と \(U_j\) が共通部分を持つか

上記の中に持つものがあった場合はそれぞれ \(i\) または \(10+j\) が答えであり、いずれも共通部分を持たなかった場合は \(-1\) を出力すれば良いです。

さて、時間計算量について、\((K/2)\) 回以下の操作で作ることのできる状態を列挙するのにはマス目の操作も考えて \(O(3^{K/2}\cdot N^2)\) となります。さらに、集合に対する存在判定は、状態の比較に \(O(HW)\) かかるとすると、\(1\) 回あたり\(O(HW\log(3^{K/2}))=O(KHW)\) かかり、この判定を \(3\cdot 4^{K/2-1}\) 回行うことになるので全体での計算量は \(O(3^{K/2}\cdot KHW)\) となります。今回 \(K=20\), \(H,W\leq 8\) であることから、\(3^{K/2}\cdot KHW\sim 8\times 10^7\) 程度であり、時間制限が \(5\) 秒であることも踏まえると十分間に合います。
よってこの問題を解く事ができました。

なお、各マスに書かれている数字から \(1\) を引けば各マスの状態は \(6\) bit で扱う事ができ (\(HW\leq 64=2^6\) のため) 、マス目の状態は高々 \(6\times 64=384\) bitで表す事ができます。これを用いてマス目の状態を管理する方法を工夫する事で、より高速にこの問題を解く事ができます。

c++ による実装例

#include <bits/stdc++.h>
using namespace std;

#define vi  vector<int>
#define vvi vector<vector<int> >
#define rep(i, n) for(int i = 0; i < n; ++i)

int main() {
	int h,w;
	set<vvi>t[11],u[11];
	set<vvi>::iterator itr_t[11],itr_u[11];

	cin>>h>>w;
	vvi T(h,vi(w)),U(h,vi(w)),v(h,vi(w));
	vi tmp(w);
	int x,y,z;

	rep(i,h)rep(j,w)cin>>T[i][j];
	rep(i,h)rep(j,w)U[i][j]=(i*w)+j+1;
	if(T==U){
		cout<<0<<endl;
		return 0;
	}

	t[0].insert(T);
	rep(i,10){
		itr_t[i]=t[i].begin();
		while(itr_t[i]!=t[i].end()){
			v=*(itr_t[i]);
			rep(xx,2)rep(yy,2){
				rep(i,h/2)rep(j,w-1){
					swap(v[i+xx][j+yy],v[h-2-i+xx][w-2-j+yy]);
					if(i*(w-1)+j+1>=((h-1)*(w-1))/2)break;
				}

				if(v==U){
					cout<<(i+1)<<endl;
					return 0;
				}
				if((t[i].count(v)==0)&&((i==0)||(t[i-1].count(v)==0)))t[i+1].insert(v);

				rep(i,h/2)rep(j,w-1){
					swap(v[i+xx][j+yy],v[h-2-i+xx][w-2-j+yy]);
					if(i*(w-1)+j+1>=((h-1)*(w-1))/2)break;
				}
			}
			itr_t[i]++;
		}
	}

	u[0].insert(U);
	rep(i,10){
		itr_u[i]=u[i].begin();
		while(itr_u[i]!=u[i].end()){
			v=*(itr_u[i]);
			rep(xx,2)rep(yy,2){
				rep(i,h/2)rep(j,w-1){
					swap(v[i+xx][j+yy],v[h-2-i+xx][w-2-j+yy]);
					if(i*(w-1)+j+1>=((h-1)*(w-1))/2)break;
				}

				if(t[10].count(v)==1){
					cout<<(i+11)<<endl;
					return 0;
				}
				if((u[i].count(v)==0)&&((i==0)||(u[i-1].count(v)==0)))u[i+1].insert(v);

				rep(i,h/2)rep(j,w-1){
					swap(v[i+xx][j+yy],v[h-2-i+xx][w-2-j+yy]);
					if(i*(w-1)+j+1>=((h-1)*(w-1))/2)break;
				}
			}
			itr_u[i]++;
		}
	}

	cout<<-1<<endl;
	return 0;
}