ZOJ 1249 Pushing Boxes

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1249
   タイトルの大まかな意味は、1つのR*Cのmazeを与えて、その中にそれぞれ1人がいて、1つの箱と1つの箱が押す目標点、その他の格子は歩くことができることと歩くことができないことの2種類に分けて、今与えられた情況の下で人が箱を押して目標点まで最小で必要なステップ数を求めることを要求します.
   考え方:BFS＋優先キュー.人と箱の位置を1つの状態とし、ここでは1つの点の座標を20進数で1つの数に圧縮し、2次元配列で重みを判断することができます.優先キューが取り出すたびに最小のステップ数.
コード:

/*
BFS+     
*/
#include
#include
#include
#define Base 20
using namespace std ;
int R,C;
struct point{
	int r,c ;
	point(){}
	point(int rr ,int cc) 
	: r(rr) , c(cc){} 
	bool operator =(point a){
		r = a.r ; c = a.c ;	
	}
	int Zip(){
		int res = 0 ;
		res = r * Base + c ;
		return res ;		
	}	
	void Unzip(int num){
		c = num % Base ;
		r = num / Base ;	
	}
}S,Box,Target,you_pos,box_pos,n_p1,n_p2;
struct State{
	int p_num,t_num ;	
	int num1 , num2 ;
	State(){}
	State(int a,int b ,int c , int d)
	:num1(a) , num2(b) , p_num(c) , t_num(d) {}
	friend bool operator < (State s1 , State s2){
		if(s1.p_num == s2.p_num)	return s1.t_num > s2.t_num ;
		else return s1.p_num > s2.p_num ;	
	} 
};
char map[21][21] ;
bool vis[400][400] ;
int way[400][400] ;
int dr[4] = {0,0,1,-1} ;	//  ，  ，  ，  
int dc[4] = {1,-1,0,0} ;
int re_dr[4] = {0,0,-1,1} ;
int re_dc[4] = {-1,1,0,0} ;
priority_queue que ;
char dir[4] = {'e','w','s','n'} ;

void PRINT(int zip1,int zip2){
	point p1, p2 ,n_p1,n_p2;
	p1.Unzip(zip1); 	p2.Unzip(zip2);
	int w = way[zip1][zip2] ,z1,z2;
	if(w == -1)	return ;
	n_p1.r = p1.r + re_dr[w%4] ;
	n_p1.c = p1.c + re_dc[w%4] ;
	if(w >= 4){
		n_p2.r = p2.r + re_dr[w%4] ;
		n_p2.c = p2.c + re_dc[w%4] ;
	}
	else 
		n_p2 = p2 ;
	z1 = n_p1.Zip() ; z2 = n_p2.Zip() ;
	PRINT(z1,z2);
	if(w >= 4){
		printf("%c",dir[w%4]-32);	
	}
	else 
		printf("%c",dir[w%4]);
}
bool bfs(){
	State s1 ;
	point p1, p2 ;
	int zip1 , zip2 ,push , total ,z1,z2;
	memset(vis,0,sizeof(vis));
	memset(way,-1,sizeof(way));
	while(!que.empty())	que.pop() ;
	zip1 = S.Zip() ; zip2 = Box.Zip() ;
	que.push( State(zip1,zip2,0,0) );
	vis[zip1][zip2] = 1 ;
	while(!que.empty()){
		s1 = que.top();	que.pop() ;
		zip1 = s1.num1 ; zip2 = s1.num2 ; 
		push = s1.p_num ; total = s1.t_num ;
		
		you_pos.Unzip(zip1);	box_pos.Unzip(zip2); 
		if(box_pos.r==Target.r && box_pos.c==Target.c){
			PRINT(zip1,zip2);
			printf("
");
			return true ;
		}
		
		for(int i=0;i<4;i++){	
			int nr = you_pos.r + dr[i] ;
			int nc = you_pos.c + dc[i] ;
			if(nr<0 || nc<0 || nr>=R || nc>=C || map[nr][nc]=='#')	continue ;
			if(box_pos.r==nr && box_pos.c==nc){ 
				if(nr+dr[i]<0 || nr+dr[i]>=R || nc+dc[i]<0 || nc+dc[i]>=C || map[nr+dr[i]][nc+dc[i]]=='#')	continue ;
				p1.r = nr ; p1.c = nc ;
				p2.r = nr + dr[i] ; p2.c = nc + dc[i] ;
				z1 = p1.Zip() ; z2 = p2.Zip() ; 
				if(vis[z1][z2])	continue ;
				vis[z1][z2] = 1 ;
				que.push( State(z1,z2,push+1,total+1)) ;
				way[z1][z2] = i + 4 ;
			}
			else{
				p1.r = nr ; p1.c = nc ;
				p2 = box_pos ;
				z1 = p1.Zip() ; z2 = p2.Zip() ;
				if(vis[z1][z2])	continue ;
				vis[z1][z2] = 1 ;
				que.push( State(z1,z2,push,total+1));
				way[z1][z2] = i ;	
			}		
		}
	}
	return false ;
}
int main(){
	int cas = 1 ;
	while(scanf("%d %d",&R,&C) && (R+C)){
		for(int i=0;i