P1379， 一直RE， 请dalao执政球球了。

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int x;
	int y;
	int sum;
	string mxq;
};
string s;
queue<Node>q[3];
map<string, int>m[3];
int X, Y;
string stop = "123804765";
const int dx[5] = {1, -1, 0, 0};
const int dy[5] = {0, 0, 1, -1};
void expand(int i)
{
	Node f = q[i].front();
	q[i].pop();
	string st = f.mxq ;
	if(m[1 - i].count(st) != 0)
	{
		cout << f.sum + m[1 - i][st] << endl;
		exit(0);
	}
	int x = f.x ;
	int y = f.y ;
	int wh = x * 3 + y;
	for(int i = 0; i <= 3; i++)
	{
		int X = x + dx[i];
		int Y = y + dy[i];
		int wh1 = X * 3 + Y;
		if(X >= 0 && X <= 2 && Y >= 0 && Y <= 2)
		{
			swap(st[wh], st[wh1]);
			if(m[i].count(st) == 0)q[i].push((Node){X, Y, f.sum + 1, st}),m[i][st] = f.sum + 1;
			swap(st[wh], st[wh1]);
		}
	}
}
int main()
{
	cin >> s;
	for(int i = 0; i < s.size(); i ++)
	{
		if(s[i] == '0')
		{
			int x = i / 3;
			int y = i % 3;
			q[0].push((Node){x, y, 0, s});
			m[0][s] = 0;
		}
	}
	for(int i = 0; i < stop.size(); i ++)
	{
		if(stop[i] == '0')
		{
			int x = i / 3;
			int y = i % 3;
			q[1].push((Node){x, y, 0, stop});
			m[1][stop] = 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);
	}
	return 0;
}