https://www.luogu.com.cn/problem/P1379

TLE Code:

#include<bits/stdc++.h>
using namespace std;
string c,s="123804765";
short x,ans=9999,step,vis[9][9][9][9][9][9][9][9];
void dfs(int x){
	if(step>ans) return;
	vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']=step;
	if(c==s){ans=min(ans,step);return;}
	if(x==0){
		step++;
		swap(c[0],c[1]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(1);
		swap(c[0],c[1]);
		swap(c[0],c[3]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step)  dfs(3);
		swap(c[0],c[3]);
		step--;
	}
	else if(x==1){
		step++;
		swap(c[1],c[0]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(0);
		swap(c[1],c[0]);
		swap(c[1],c[4]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(4);
		swap(c[1],c[4]);
		swap(c[1],c[2]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(2);
		swap(c[1],c[2]);
		step--;
	}
	else if(x==2){
		step++;
		swap(c[2],c[1]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(1);
		swap(c[2],c[1]);
		swap(c[2],c[5]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(5);
		swap(c[2],c[5]);
		step--;
	}
	else if(x==3){
		step++;
		swap(c[3],c[0]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(0);
		swap(c[3],c[0]);
		swap(c[3],c[4]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(4);
		swap(c[3],c[4]);
		swap(c[3],c[6]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(6);
		swap(c[3],c[6]);
		step--;
	}
	else if(x==4){
		step++;
		swap(c[4],c[1]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(1);
		swap(c[4],c[1]);
		swap(c[4],c[3]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(3);
		swap(c[4],c[3]);
		swap(c[4],c[5]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(5);
		swap(c[4],c[5]);
		swap(c[4],c[7]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(7);
		swap(c[4],c[7]);
		step--;
	}
	else if(x==5){
		step++;
		swap(c[5],c[2]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(2);
		swap(c[5],c[2]);
		swap(c[5],c[4]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(4);
		swap(c[5],c[4]);
		swap(c[5],c[8]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(8);
		swap(c[5],c[8]);
		step--;
	}
	else if(x==6){
		step++;
		swap(c[6],c[3]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(3);
		swap(c[6],c[3]);
		swap(c[6],c[7]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(7);
		swap(c[6],c[7]);
		step--;
	}
	else if(x==7){
		step++;
		swap(c[7],c[4]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(4);
		swap(c[7],c[4]);
		swap(c[7],c[6]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(6);
		swap(c[7],c[6]);
		swap(c[7],c[8]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(8);
		swap(c[7],c[8]);
		step--;
	}
	else {
		step++;
		swap(c[8],c[5]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(5);
		swap(c[8],c[5]);
		swap(c[8],c[7]);
		if(vis[c[0]-'0'][c[1]-'0'][c[2]-'0'][c[3]-'0'][c[4]-'0'][c[5]-'0'][c[6]-'0'][c[7]-'0']>step) dfs(7);
		swap(c[8],c[7]);
		step--;
	}
}
int main(){
	memset(vis,0x3f,sizeof(vis));
    for(int i=0;i<9;i++){
    	cin>>c[i];
    	if(c[i]=='0') x=i;
    }
    dfs(x);
    cout<<ans<<endl;
    return 0;
}