DEV-C++测没问题，洛谷就CE，真的服了：

#include<bits/stdc++.h>
using namespace std;
struct node{
	string s;
	int pos;
}start,end;
map<string,int>mp[2];
queue<node>q[2];
int main(){
	cin>>start.s;
	end.s="123804765";
	for(int i=0;i<9;i++){
		if(start.s[i]=='0') start.pos=i;
	}
	end.pos=4;
	q[0].push(start);
	q[1].push(end);
	mp[0][start.s]=1;
	mp[1][end.s]=1;
	int op=0;
	while(1){
		node x=q[op].front();
		q[op].pop();
		if(mp[1-op][x.s]){
			cout<<mp[op][x.s]+mp[1-op][x.s]-2;
			return 0;
		}
		for(int i=0;i<4;i++){
			node y=x;
			if(i==0){
				if(y.pos==2||y.pos==5||y.pos==8) continue;
				swap(y.s[x.pos],y.s[x.pos+1]);
				y.pos++;
				if(mp[op][y.s]) continue;
				mp[op][y.s]=mp[op][x.s]+1;
				q[op].push(y);
			}
			else if(i==1){
				if(y.pos==0||y.pos==3||y.pos==6) continue;
				swap(y.s[x.pos],y.s[x.pos-1]);
				y.pos--;
				if(mp[op][y.s]) continue;
				mp[op][y.s]=mp[op][x.s]+1;
				q[op].push(y);
			}
			else if(i==2){
				if(y.pos==0||y.pos==1||y.pos==2) continue;
				swap(y.s[x.pos],y.s[x.pos-3]);
				y.pos-=3;
				if(mp[op][y.s]) continue;
				mp[op][y.s]=mp[op][x.s]+1;
				q[op].push(y);
			}
			else{
				if(y.pos==6||y.pos==7||y.pos==8) continue;
				swap(y.s[x.pos],y.s[x.pos+3]);
				y.pos+3;
				if(mp[op][y.s]) continue;
				mp[op][y.s]=mp[op][x.s]+1;
				q[op].push(y);
			}
		}
		op=1-op;
	}
	return 0;
}

双向bfs，求调