This problem can be solved with meet-in-the-middle trick.

First, we consider if one can make the target grid with \(20\) or fewer operations.

Since there are four possible moves in one operation, there are at most \(4^K\) states that can be obtained by \(K\) or less operations. Moreover, rotating the same region consecutively reverts the operation, so the count is at most \(4\cdot 3^{K-1}\). However, there are at most \(4\cdot 3^{19}\) \((\simeq 5\cdot 10^9)\) states that can be obtained under the constraints here, which are almost impossible to enumerate.

Here, since the operation is a \(180\)-degree rotation, the inverse is the operation itself; thus, the states from which the target state can be obtained with \(K\) or less operations coincide with the set of operations that can be obtained by applying \(K\) or less operations from the target state.
Therefore, for the set of states \(T\) and \(U\) that can be obtained with \(10\) or less moves from the initial and target states, respectively, if \(T\) and \(U\) has a non-empty intersection, i.e. if there exists a state that is reachable from both the initial and target state with \(10\) or less moves, then one can make the target state with \(20\) states via that state; otherwise, it is impossible to do so.

Next, let us consider how to determine the minimum number of operations required; this can be similarly solved by partitioning the sets \(T\) and \(U\) mentioned above. For \(i=0,1,\ldots,10\), let \(T_i\) be the set of states that cannot be obtained with \((i-1)\) or less operations, but can be obtained with \(i\) operations. (Here, \(T_0\) is the set only consisting of the initial state.) Likewise, let \(U_i\) \((0\leq i\leq 10)\) be the set of states that can be obtained with exactly \(i\) operation but not less; then the answer is the minimum \((i+j)\) such that \(T_i\) and \(U_j\) have non-empty intersection.

In reality, if \(T_i\) and \(U_j\) have an intersection, then by definition any \(T_{i'}\) and \(U_{j'}\) satisfying \(i+j=i'+j'\) do, so it is sufficient to check one combination for each \(i+j\); for example, it is sufficient to check the following two:

• For each \(i=0,1,\ldots,10\), check if \(T_i\) and \(U_0\) have an intersection.
• For each \(j=1,2,\ldots, 10\), check if \(T_{10}\) and \(U_j\) have an intersection.

If any of above do, then \(i\) or \(10+j\) is the answer; otherwise, you may print \(-1\).

Regarding time complexity, it costs \(O(3^{K/2}\cdot N^2)\) time to enumerate states obtained with \((K/2)\) or less operations. Checking the existence of an element costs \(O(HW\log(3^{K/2}))=O(KHW)\) each if comparing states requires \(O(HW)\) time, for a total of \(O(3^{K/2}\cdot KHW)\) time. In this problem, \(K=20\) and \(H,W\leq 8\), so \(3^{K/2}\cdot KHW\sim 8\times 10^7\); since the execution time limit is \(5\) seconds, it is fast enough.
Therefore, the problem has been solved.

Note that, if you subtract one from the digit written on each square, the state of each square can be represented by \(6\) bits (because \(HW\leq 64=2^6\)), so that the state of a grid is represented with at most \(6\times 64=384\) bits. With this trick on managing states, the problem can be solved faster.

Sample code in 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;
}