题目

#include<bits/stdc++.h>
using namespace std;
map<int,bool>vis;
string x;int cnt;
queue<pair<string,int> >f;
int d[4]={1,-1,3,3};
int num(string x){
	int ans;
	stringstream change;
		change<<x;
		change>>ans;
	return ans;
}
int main(){
	cin>>x;
	f.push({x,0});vis[num(x)]=true;
	while(!f.empty()){
		x=f.front().first;
		cnt=f.front().second;
		f.pop();
		if(x=="123804765"){
			cout<<cnt;
			return 0;
		}
		for(int i=1;i<=8;++i){
			int id=0;
			for(int j=0;j<8;++j)
				if(x[j]==char(i+'0'))
					id=j;
			for(int i=0;i<4;++i){
				if((id%3==1&&i==1)||(id%3==0&&i==0)||id+d[id]<0||id+d[id]>=8)
					continue;
				string y=x;
				swap(y[id],y[id+d[i]]);
				if(!vis[num(y)]){
					vis[num(y)]=1;
					f.push({y,cnt+1});
				}
			}
		}
	}
}

提交记录