纯暴力bfs 直接过了

#include<bits/stdc++.h>
using namespace std;
struct node
{
	string s;int num;int sum;
	node()
	{
		s="";
		num=0;sum=0;
	}
};

int d[5]={0,-1,1,3,-3};
string ans="123804765";
int main()
{
 	freopen("in.txt","r",stdin);
	node chu;
	map<string,int> mp;
	/*for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
	{
		char c;
		cin>>c;
	}*/
	cin>>chu.s;
	for(int i=0;i<chu.s.size();i++)
	if(chu.s[i]=='0') chu.num=i;
	queue<node> q;
	q.push(chu);
	while(!q.empty())
	{
		node lin=q.front();
		q.pop();
//		cout<<lin.s<<endl; 
		if(lin.s==ans) 
		{
			cout<<lin.sum<<endl;
			return 0;
		}
		if(mp[lin.s]!=10) mp[lin.s]=10;
		else
		{
//			delete(lin);
			continue;
		}
        for(int i=1;i<=4;i++)
        {
        	if((lin.num==2 || lin.num==5) && d[i]==1) continue;
        	if((lin.num==3 || lin.num==6) && d[i]==-1) continue;
        	if(lin.num+d[i]<0 || lin.num+d[i]>8) continue;
        	node t=lin;
        	swap(t.s[t.num],t.s[t.num+d[i]]);
        	t.num+=d[i];
        	t.sum++;
        	q.push(t);
//        	delete(t);
		}
	}
}