RT，大家都会的普通dfs，有什么优化方法，还是就是过不了

#include<iostream>
#include<map>
#include<queue>
#include<cstdio>
#include<cmath>
#include<cstring>
#define re register int
using namespace std;
string str;
bool vis[2000005];
int pre1[2000005];
string pre2[2000005];
string a[15]={"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
int maxstep=0x7fffffff;
string temp;
int c(string s)
{
	int res=0,l=s.size();
	for(int i=l-1;i>=0;i--)
	{
		res+=(s[i]-'0')*pow(4,l-1-i);
	}
	return res;
}
struct node
{
	string x;
	int step;
}now,top;
void bfs()
{
	queue <node> q;
	vis[c(str)]=1;
	now.x=str; now.step=0;
	q.push(now);
	while(!q.empty())
	{
		top=q.front();
		q.pop();
		if(top.x=="333333333")
		{
			string t=top.x;
			while(pre2[c(t)]!="")
			{
				temp+=(char)(pre1[c(t)]+'0');
				t=pre2[c(t)];
			}
			return;
		}
		now.step=top.step+1;
		for(int i=0;i<9;i++)
		{
			now.x=top.x;
			for(int j=0;j<a[i].size();j++)
			{
				now.x[a[i][j]-'A']++;
				if(now.x[a[i][j]-'A']=='4')
					now.x[a[i][j]-'A']='0';
			}
	//		cout<<c(now.x)<<endl;
			if(!vis[c(now.x)])
			{
				vis[c(now.x)]=1;
				pre1[c(now.x)]=i+1;
				pre2[c(now.x)]=top.x;
				q.push(now);
			}
		}
	}
}
int main()
{
	
	for(re i = 1; i <= 9 ; ++i){
		short x;
		scanf("%d" , &x );
		str += (char)(x / 3 -1 + '0');
	}	
	bfs();
	for(int i=temp.size()-1;i>=0;i--) cout<<temp[i]<<" ";
}