Source Code

Problem: 3131  User: yzhw 
Memory: 35704K  Time: 2250MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <set>
# include <queue>
# define _get(a,b) (((a)>>(3*(8-(b))))&7)
# define _change(a,b,c) ((a)=(((a)&mask[(b)])|((c)<<(3*(8-(b))))))
using namespace std;
unsigned int ori[9],mask[9],refer[9][80000],*ans;
unsigned int used[8000000];
int _next[8][2]={0,0,0,0,6,5,4,7,3,6,7,2,2,4,5,3};
queue<unsigned int> q1;
queue<char> q2;
int chk(unsigned int pos)
{
    pos>>=5;
    int p=pos%79999;
	while(ans[p]!=0xffffffff&&(ans[p]>>5)!=(pos))
		p=(p+1)%80000;
	if ((ans[p]>>5)==(pos))
		return ans[p]&31;
	else
		return -1;
	
}
bool gethash(unsigned int pos)
{
	int p=pos%7999999;
	while(used[p]!=0xffffffff&&(used[p])!=pos)
		p=(p+1)%8000000;
   return used[p]==pos;
}
void puthash(unsigned int pos)
{
	int p=(pos)%7999999;
	while(used[p]!=0xffffffff)
		p=(p+1)%8000000;
	used[p]=pos;
}
//int ccount=0;
void make_bfs(unsigned int s,int limit)
{
	unsigned int tmp;
	int p;
	while(!q1.empty())
		q1.pop();
	q1.push(s);
	p=(s>>5)%79999;
    while(ans[p]!=0xffffffff)
		p=(p+1)%80000;
	ans[p]=s;
	while(!q1.empty())
	{
		tmp=q1.front();
		q1.pop();
		if((tmp&31)>=limit) continue;
		s=(tmp>>5);
		int e=0;
		for(int i=0;i<9;i++)
			if(_get(s,i)==1)
			{
				e=i;
				break;
			}
		
		if(e/3!=0)
		{
			_change(s,e,_next[_get(s,e-3)][0]);
			_change(s,e-3,1);
	        if(chk(((s<<5)|((tmp&31)+1)))==-1)
			{
				p=s%79999;
				while(ans[p]!=0xffffffff)
					p=(p+1)%80000;
				ans[p]=((s<<5)|((tmp&31)+1));
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e-3,_next[_get(s,e)][0]);
			_change(s,e,1);
		}
		if(e/3!=2)
		{
			_change(s,e,_next[_get(s,e+3)][0]);
			_change(s,e+3,1);
	        if(chk(((s<<5)|((tmp&31)+1)))==-1)
			{
				p=s%79999;
				while(ans[p]!=0xffffffff)
					p=(p+1)%80000;
				ans[p]=((s<<5)|((tmp&31)+1));
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e+3,_next[_get(s,e)][0]);
			_change(s,e,1);
		}
		if(e%3!=0)
		{
			_change(s,e,_next[_get(s,e-1)][1]);
			_change(s,e-1,1);
			if(chk(((s<<5)|((tmp&31)+1)))==-1)
			{
				p=s%79999;
				while(ans[p]!=0xffffffff)
					p=(p+1)%80000;
				ans[p]=((s<<5)|((tmp&31)+1));
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e-1,_next[_get(s,e)][1]);
			_change(s,e,1);
		}
		if(e%3!=2)
		{
			_change(s,e,_next[_get(s,e+1)][1]);
			_change(s,e+1,1);
			if(chk(((s<<5)|((tmp&31)+1)))==-1)
			{
				p=s%79999;
				while(ans[p]!=0xffffffff)
					p=(p+1)%80000;
				ans[p]=((s<<5)|((tmp&31)+1));
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e+1,_next[_get(s,e)][1]);
			_change(s,e,1);
		}
	}
}
int bfs()
{
	unsigned int tmp;
	if(chk(q1.front())!=-1)
		return chk(q1.front());
	while(!q1.empty())
	{
		tmp=q1.front();
		q1.pop();
		if((tmp&31)>=12) continue;
		int s=(tmp>>5);
		int e=0;
		for(int i=0;i<9;i++)
			if(_get(s,i)==1)
			{
				e=i;
				break;
			}
		if((tmp&31)>=30) continue;
		if(e/3!=0)
		{
			_change(s,e,_next[_get(s,e-3)][0]);
			_change(s,e-3,1);
			int len=chk(s<<5);
			if(len!=-1)
				return (tmp&31)+1+len;
			if(!gethash(s))
			{
				puthash(s);
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e-3,_next[_get(s,e)][0]);
			_change(s,e,1);
		}
		if(e/3!=2)
		{
			_change(s,e,_next[_get(s,e+3)][0]);
			_change(s,e+3,1);
			int len=chk(s<<5);
			if(len!=-1)
				return (tmp&31)+1+len;
			if(!gethash(s))
			{
				puthash(s);
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e+3,_next[_get(s,e)][0]);
			_change(s,e,1);
		}
		if(e%3!=0)
		{
			_change(s,e,_next[_get(s,e-1)][1]);
			_change(s,e-1,1);
			int len=chk(s<<5);
			if(len!=-1)
				return (tmp&31)+1+len;
			if(!gethash(s))
			{
				puthash(s);
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e-1,_next[_get(s,e)][1]);
			_change(s,e,1);
		}
		if(e%3!=2)
		{	
			_change(s,e,_next[_get(s,e+1)][1]);
			_change(s,e+1,1);
			int len=chk(s<<5);
			if(len!=-1)
				return (tmp&31)+1+len;
			if(!gethash(s))
			{
				puthash(s);
				q1.push((s<<5)|((tmp&31)+1));
			}
			_change(s,e+1,_next[_get(s,e)][1]);
			_change(s,e,1);
		}
	}
	return -1;
}
void init()
{
   for(int i=0;i<9;i++)
   {
     ori[i]=0;
     for(int j=0;j<i;j++)
     {
        ori[i]<<=3;
        ori[i]|=2;
     }
     ori[i]<<=3;
     ori[i]|=1;
     for(int j=i+1;j<9;j++)
     {
        ori[i]<<=3;
        ori[i]|=2;
     }
   }
   for(int i=0;i<9;i++)
   {
      mask[i]=0;
      for(int j=0;j<i;j++)
      {
         mask[i]<<=3;
         mask[i]|=7;
      }
      mask[i]<<=3;
      for(int j=i+1;j<9;j++)
      {
         mask[i]<<=3;
         mask[i]|=7;
      }
   }
   for(int i=0;i<9;i++)
	     for(int j=0;j<80000;j++)
			 refer[i][j]=0xffffffff;
   for(int i=0;i<9;i++)
   {
	   ans=refer[i];
	   make_bfs(ori[i]<<5,18);
   }
}
int minnum=0xfffffff;

void make_end(char *str,int l,unsigned int num)
{
    if(l==9)
	{
		int len=chk(num<<5);
		if(len!=-1&&len<=minnum)
		{
			minnum=len;
			while(!q1.empty())
				q1.pop();
		}
		q1.push(num<<5);
		puthash(num);
	}
	else
	{
		num<<=3;
		switch(*str)
		{
		case 'W':
			make_end(str+1,l+1,num|2);
			make_end(str+1,l+1,num|3);
			break;
		case 'B':
			make_end(str+1,l+1,num|4);
			make_end(str+1,l+1,num|5);
			break;
		case 'R':
			make_end(str+1,l+1,num|6);
			make_end(str+1,l+1,num|7);
			break;
		case 'E':
			make_end(str+1,l+1,num|1);
			break;
		};
	}
}
int main()
{
    int r,c;
    init();
    while(cin>>c>>r)
    {
       if(!c&&!r) break;
       c--;
       r--;
	   minnum=0xfffffff;
	   char tar[10];
       for(int i=0;i<9;i++)
       {
         cin>>tar[i];
       }
	   ans=refer[r*3+c];
	   for(int i=0;i<8000000;i++)
		  used[i]=0xffffffff;
	   while(!q1.empty())
		    q1.pop();
	
	   make_end(tar,0,0);
	   cout<<bfs()<<endl;
		    
    }
    return 0;
}