poj 1324-Holedox Moving-状態圧縮+BFS

素朴で暴力的な方法でやった...
現在のヘビ体と前の部分のヘビ体の位置関係を1つの1 2 3 4で表し、ヘビは最長7であるため、4進数で状態を表すことができ、各ヘビ頭、そのヘビ体は4^7種類の状態がある.
TLEの計算が繰り返されないように、状態圧縮マークが表示された状態で...
他にも地味なBFS...
書き方が挫けている.ステータス配列はboolを開いてから通過します.そうしないとtle
もちろん本題は双方向bfs,A*アルゴリズムも使えます.の
素朴なアルゴリズムに基づいてbitsetで状態を表すと3000 kbの空間が節約され、時間は3.8 sも差がない.
 
以下は素朴な方法です:3.9 s... 10520kb

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
struct node
{
	int hx,hy;
	int body[8]; //1 2 3 4          
	int step;
};
int len;
int n,m,l;
queue<node> qq;
int dirx[]={0,0,1,-1}; //you  zuo xia shang
int diry[]={1,-1,0,0};
int mp[22][22];
bool state[22][22][1<<14];
int trans(int x,int y)			//  del_x,del_y     
{
	if (x==-1&&y==0)
		return 1;  //shang 
	if (x==1&&y==0)	
		return 2; // 
	if (x==0&&y==-1)
		return 3 ;		// 
	if (x==0&&y==1)
		return 4;	// 
}
node move_to(node t,int x,int y)		//    [X,Y]        
{
	node res;
	int i;
	for (i=len;i>1;i--)
	{
		res.body[i]=t.body[i-1];
	}
	int dir=trans(t.hx-x,t.hy-y);
 
		res.body[1]=dir;  
	res.step=t.step+1;
	res.hx=x;
	res.hy=y;
	return res;
	
}
inline void get_xy(int &tx,int &ty,int dir,int x,int y)		//     
{
	if (dir==1)// 
	{
		tx=x-1;ty=y;
	}
	if (dir==2)//xia
	{
		tx=x+1;ty=y;
	}
	if (dir==3)//zuo
	{
		tx=x;ty=y-1;
	}
	if (dir==4)//you
	{
		tx=x;ty=y+1;
	}
 return ;

}
void deal_map(node t)		//        
{
	int i;
	int lastx,lasty;
	for (i=1;i<=len;i++)
	{
		int tx,ty;
		if (i==1)
		{
			get_xy(tx,ty,t.body[i],t.hx,t.hy);
		}
		else
		{
			get_xy(tx,ty,t.body[i],lastx,lasty);
		}
			lastx=tx;
			lasty=ty;
		if (mp[tx][ty]==0)
			mp[tx][ty]=2;	 
	}
		
}
void un_deal_map(node t)		//       
{
int i;
	int lastx,lasty;
	for (i=1;i<=len;i++)
	{
		int tx,ty;
		if (i==1)
		{
			get_xy(tx,ty,t.body[i],t.hx,t.hy);  
		}
		else
		{
			get_xy(tx,ty,t.body[i],lastx,lasty);
		}
			lastx=tx;
			lasty=ty;
		if (mp[tx][ty]==2)
			mp[tx][ty]=0;	 
	}
}
int get_body_num(node &y)  //        
{
	int i;
	int ret=0;
	for (i=1;i<=len;i++)
	{
	//	ret+=(y.body[i]-1)*  int(pow(4.0,i-1));         
	 	ret+=(y.body[i]-1)*  1<<(2*(i-1)) ;  //     
	}
	return ret;
}

int main()
{
	int cnt=1;
	while(scanf("%d%d%d",&n,&m,&l)!=EOF)
	{
		if (!n&&!m&&!l) break;
		while(!qq.empty())
			qq.pop();
		node tm;
		memset(mp,0,sizeof(mp)); 
		 memset(state,0,sizeof(state));
		int i; 
		scanf("%d%d",&tm.hx,&tm.hy);
		for (i=0;i<=m+1;i++)   //lock the board        
			mp[0][i]=1;
		for (i=0;i<=m+1;i++)
			mp[n+1][i]=1;
		for (i=0;i<=n+1;i++)
			mp[i][0]=1;
		for (i=0;i<=n+1;i++)
			mp[i][m+1]=1;  
			int xx,yy;
		 
		int lastx,lasty;
		int delx,dely;
		for (i=1;i<=l-1;i++)
		{
			scanf("%d%d",&xx,&yy);
			if (i==1) 
			{
				delx=xx-tm.hx;
				dely=yy-tm.hy;
			}
			else
			{
				delx=xx-lastx;
				dely=yy-lasty;
			}
			tm.body[i]=trans(delx,dely);		//                 
			lastx=xx;
			lasty=yy;
		}
		len=l-1;
		int num;	
	
		scanf("%d",&num);
		for (i=1;i<=num;i++) 
		{
			scanf("%d%d",&xx,&yy);
			mp[xx][yy]=1;			//    
		}
////

	 
		tm.step=0;
		int ret=get_body_num(tm);
		state[tm.hx][tm.hy][ret]=true;	
		qq.push(tm); 
		int ans=-1;
		while(!qq.empty())
		{
			node t=qq.front();
			qq.pop();
			if (t.hx==1&&t.hy==1)		//    
			{
				ans=t.step;
				break;
			}
			deal_map(t);		//      
			for (i=0;i<4;i++)
			{
				int x=t.hx+dirx[i];
				int y=t.hy+diry[i];
				if (mp[x][y]) continue;			//      
				node res=move_to(t,x,y);		//         res
				int ret=get_body_num(res);		//           
				if (state[res.hx][res.hy][ret]==true)		
					continue;
				state[res.hx][res.hy][ret]=true;
				qq.push(res);				

			}
			un_deal_map(t);		//    
		}
		
		printf("Case %d: %d
",cnt++,ans);
	}
	return 0;
	
}