rt,此为测评记录

问题：不论我怎么判重+long long，最后一个点总是WA，比答案多1 (QWQ)

#include <bits/stdc++.h>
#define int long long
using namespace std;
string se[2]={"","012345678"};
struct State{
	int step;
	string state;
	State(int step,string state):step(step),state(state){};
};
queue<State>q[2];
map<string,int>ans[2];
map<string,string>from[2];
void p(string x){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cout<<x[i*3+j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
void print(string mid){
	map<string,string>next;
	string tmp=mid;
	while(from[0].count(tmp)){
		next[from[0][tmp]]=tmp;
		tmp=from[0][tmp];
	}
	tmp=se[0];
	while(tmp!=mid){
		p(tmp);
		tmp=next[tmp];
	}
	while(tmp!=se[1]){
		p(tmp);
		tmp=from[1][tmp];
	}
	p(tmp);
}
void expand(int d){
	State tmp=q[d].front();
	q[d].pop();
	string t=tmp.state;
	if(ans[d^1].count(t)||t==se[d^1]){
		cout<<tmp.step+ans[d^1][t]<<endl;
		print(t);
		exit(0); 
	}
	/*012345678
	->125048378*/
	if(d==0){
		t[0]=tmp.state[3];
		t[1]=tmp.state[0];
		t[2]=tmp.state[1];
		t[3]=tmp.state[6];
		t[5]=tmp.state[2];
		t[6]=tmp.state[7];
		t[7]=tmp.state[8];
		t[8]=tmp.state[5];
	} else{
		t[0]=tmp.state[1];
		t[1]=tmp.state[2];
		t[2]=tmp.state[5];
		t[3]=tmp.state[0];
		t[5]=tmp.state[8];
		t[6]=tmp.state[3];
		t[7]=tmp.state[6];
		t[8]=tmp.state[7];
	}
	if(!ans[d].count(t)&&t!=se[d]){
		q[d].push(State(tmp.step+1,t));
		ans[d][t]=tmp.step+1;
		from[d][t]=tmp.state;
	}
	t=tmp.state;
	if(d==0){
		t[3]=tmp.state[5];
		t[4]=tmp.state[3];
		t[5]=tmp.state[4];
	} else{
		t[5]=tmp.state[3];
		t[4]=tmp.state[5];
		t[3]=tmp.state[4];
	}
	if(!ans[d].count(t)&&t!=se[d]){
		q[d].push(State(tmp.step+1,t));
		ans[d][t]=tmp.step+1;
		from[d][t]=tmp.state;
	}
}
signed main(){
	for(int i=1;i<=9;i++){
		char c;
		cin>>c;
		se[0]+=c;
	} 
	q[0].push(State(0,se[0]));
	ans[0][se[0]]=0;
	q[1].push(State(0,se[1]));
	ans[1][se[1]]=0;
	while(!q[0].empty()&&!q[1].empty()){
		if(q[0].size()<q[1].size()){
			expand(0);
		} else{
			expand(1);
		}
	}
	while(!q[0].empty()) expand(0);
	while(!q[1].empty()) expand(1);
	cout<<"UNSOLVABLE"<<endl;
	return 0;
}