Language: C++

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define DIVN 3

void swap(int &a, int &b);
int fact(int a);
int dist(int x);
int abs(int x);
void insert(vector<int> &A, int v);
int extract(vector<int> &A);
int PtoI(vector<int> p);
vector<int> ItoP(int ii);
int SolvePuzzle(vector<int> P);

vector<int> Puzzles(fact(DIVN*DIVN), INT_MAX);


void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
	return;
}

int fact(int a){
	int b = 1;
	for (int i = 2; i <= a; i++){
		b = b * i;
	}
	return b;
}

int dist(int x){
	std::vector<int> P = ItoP(x);
	int result = 0;
	for (int i = 0; i < DIVN*DIVN; i++){
		result += abs(P[i] % DIVN - (i + 1) % DIVN) + abs((P[i] == 0 ? DIVN - 1 : (P[i] - 1) / DIVN) / DIVN - i / DIVN);
	}
	return -result;
}

int abs(int x){
	return x < 0 ? -x : x;
}

void insert(vector<int> &A, int v){
	int n = A.size();
	A.push_back(v);
	while (n != 0){
		int i = (n - 1) / 2;
		if (dist(A[n]) > dist(A[i])){
			swap(A[n], A[i]);
		}
		n = i;
	}
	return;
}

int extract(vector<int> &A){
	int n = A.size() - 1;
	int res = A[0];
	A[0] = A[n];
	A.pop_back();

	for (int i = 0, j; 2 * i + 1 < n;){
		j = 2 * i + 1;
		if (j != n - 1 && dist(A[j]) < dist(A[j + 1])){
			j++;
		}
		if (dist(A[i]) < dist(A[j])){
			swap(A[i], A[j]);
		}
		i = j;
	}
	return res;
}


int PtoI(vector<int> p){
	int x, result = 0;
	for (int i = 0; i < DIVN*DIVN - 1; i++){
		for (int j = 0; j < DIVN*DIVN - i; j++){
			if (p[j] == i){
				x = j;
				p.erase(p.begin() + j);
				break;
			}
		}
		result += x * fact(DIVN*DIVN - i - 1);
	}
	return result;
}

vector<int> ItoP(int ii){
	vector<int> result(DIVN*DIVN, -1);
	for (int i = 0; i < DIVN*DIVN; i++){
		int index = ii / fact(DIVN*DIVN - i - 1);
		ii = ii % fact(DIVN*DIVN - i - 1);
		int curindex = -1;
		int x = -1;
		for (int j = 0; j < DIVN*DIVN; j++){
			if (result[j] == -1){
				curindex++;
			}
			if (curindex == index) {
				x = j;
				break;
			}
		}
		result[x] = i;
	}
	return result;
}

int SolvePuzzle(vector<int> P){
	vector<int> Que;
	insert(Que, PtoI(P));
	int answer = INT_MAX;
	Puzzles[PtoI(P)] = 0;
	while (!Que.empty()){
		vector<int> Q = ItoP(extract(Que));
		int Cursor;
		bool isAligned = true;
		for (int i = 0; i < DIVN*DIVN; i++){
			if (Q[i] != (i + 1) % (DIVN*DIVN)){
				isAligned = false;
				break;
			}
		}
		if (isAligned && Puzzles[PtoI(Q)] < answer){
			answer = Puzzles[PtoI(Q)];
		}
		for (int i = 0; i < DIVN*DIVN; i++){
			if (Q[i] == 0){
				Cursor = i;
				break;
			}
		}
		vector<int> Qnext;
		if (Cursor >= DIVN){
			Qnext = Q;
			swap(Qnext[Cursor], Qnext[Cursor - DIVN]);
			if (Puzzles[PtoI(Qnext)] > Puzzles[PtoI(Q)] + 1 && (answer > Puzzles[PtoI(Q)] + 1)){
				Puzzles[PtoI(Qnext)] = Puzzles[PtoI(Q)] + 1;
				insert(Que, PtoI(Qnext));
			}
		}
		if (Cursor < DIVN * (DIVN - 1)){
			Qnext = Q;
			swap(Qnext[Cursor], Qnext[Cursor + DIVN]);
			if (Puzzles[PtoI(Qnext)] > Puzzles[PtoI(Q)] + 1 && (answer > Puzzles[PtoI(Q)] + 1)){
				Puzzles[PtoI(Qnext)] = Puzzles[PtoI(Q)] + 1;
				insert(Que, PtoI(Qnext));
			}
		}
		if (Cursor % DIVN != 0){
			Qnext = Q;
			swap(Qnext[Cursor], Qnext[Cursor - 1]);
			if (Puzzles[PtoI(Qnext)] > Puzzles[PtoI(Q)] + 1 && (answer > Puzzles[PtoI(Q)] + 1)){
				Puzzles[PtoI(Qnext)] = Puzzles[PtoI(Q)] + 1;
				insert(Que, PtoI(Qnext));
			}
		}
		if (Cursor % DIVN != DIVN - 1){
			Qnext = Q;
			swap(Qnext[Cursor], Qnext[Cursor + 1]);
			if (Puzzles[PtoI(Qnext)] > Puzzles[PtoI(Q)] + 1 && (answer > Puzzles[PtoI(Q)] + 1)){
				Puzzles[PtoI(Qnext)] = Puzzles[PtoI(Q)] + 1;
				insert(Que, PtoI(Qnext));
			}
		}
	}

	return answer;
}

int main(){
	int k;
	vector<int> P;
	for (int i = 0; i < DIVN * DIVN; i++){
		scanf("%d", &k);
		P.push_back(k);
	}
	int n = SolvePuzzle(P);

	printf("%d\n", n);

	return 0;
}


Compiler output:
a.cc:18:38: error: 'INT_MAX' was not declared in this scope
   18 | vector<int> Puzzles(fact(DIVN*DIVN), INT_MAX);
      |                                      ^~~~~~~
a.cc:4:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
    3 | #include <vector>
  +++ |+#include <climits>
    4 | using namespace std;
a.cc: In function 'int SolvePuzzle(std::vector<int>)':
a.cc:121:22: error: 'INT_MAX' was not declared in this scope
  121 |         int answer = INT_MAX;
      |                      ^~~~~~~
a.cc:121:22: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'