poj 1324 Holedox Moving A*算法對bfs的優化

poj 1324 Holedox Moving A*算法對bfs的優化

題意：

迷宮裡有一條貪食蛇，求它的蛇頭到迷宮左上角最少要多少步。

分析：

關鍵是將蛇的狀態壓縮編碼，然後bfs,超時就改A*,這題有類似最短路徑的性質，A*發現節點重復後不需要更新直接捨棄即可。

代碼：

//poj 1324
//sep9
#include 
#include 
#include 
using namespace std;

struct state
{
	int x[10],y[10];	
};
struct node
{
	int x,y,s,k,f;	
    bool operator <(const node &a) const{
    	return f>a.f;
    } 
};

int n,m,l,k,cases;
int vis[22][22][1<<15];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int g[32][32];
state start;

int encode(state s,int l)
{
	int st=0;
	for(int i=l-1;i>0;--i){
		int x,y,now;
		x=s.x[i]-s.x[i-1];
		y=s.y[i]-s.y[i-1];
		if(x==0&&y==1)
  			now=2;
		else if(x==0&&y==-1)
			now=3;
		else if(x==1&&y==0)
			now=0;
		else if(x==-1&&y==0)
			now=1;
		st<<=2;
		st|=now;
	}	
	return st;
}

state decode(int x,int y,int s,int l)
{
	int dir_num;
	state p;
	p.x[0]=x,p.y[0]=y;
	for(int i=1;i>=2;
		p.x[i]=p.x[i-1]+dir[dir_num][0];
		p.y[i]=p.y[i-1]+dir[dir_num][1];
	}
	return p;
}

node moves(node s,int d,int l)
{
	int now,x,y;
	s.x+=dir[d][0];
	s.y+=dir[d][1];
	x=-dir[d][0],y=-dir[d][1];
	if(x==0&&y==1)
  		now=2;
	else if(x==0&&y==-1)
		now=3;
	else if(x==1&&y==0)
		now=0;
	else if(x==-1&&y==0)
		now=1;
	s.s<<=2;
	s.s|=now;
	s.s&=((1<<((l-1)*2))-1);
	return s;
}

bool judge(int x,int y,int s,node pre)
{
	if(x<1||x>n||y<1||y>m) return false;
	if(vis[x][y][s]==cases) return false;
	if(g[x][y]==1) return false;	
	state ss=decode(pre.x,pre.y,pre.s,l);
	for(int i=0;i q;
	node a,tp;
	a.x=start.x[0],a.y=start.y[0];
	a.s=encode(start,l);
	a.k=0;
	a.f=a.x+a.y;
	q.push(a);
	vis[a.x][a.y][a.s]=cases;
	while(!q.empty()){
		a=q.top();q.pop();
		state tmp=decode(a.x,a.y,a.s,l);
		if(a.x==1&&a.y==1)
			return a.k;
		for(int i=0;i<4;++i){
			tp=moves(a,i,l);
			tp.k=a.k+1;
			if(!judge(tp.x,tp.y,tp.s,a)) continue;
			vis[tp.x][tp.y][tp.s]=cases;
			tp.f=tp.k+tp.x+tp.y;
			q.push(tp);
		}
	}	
	return -1;
}

int main()
{
	cases=0;
	while(scanf("%d%d%d",&n,&m,&l)==3&&(n+m+l)){
		++cases;
		for(int i=0;i