POJ 1324 Holedox Moving（我已经努力了。。）

参考了：

poj 1324 简化的贪吃蛇

在周同学的帮助下，加了个优化，总算过了，先说一下做法：
1、宽搜是必要的，那么如何记录蛇当前的状态，以避免以后重复的访问变成了关键，在这里我们将蛇的状态描述为如下三元组（x,y,state）,其中(x,y)是蛇头的坐标，state记录的是尾巴的状态，由于尾巴最长为七段，每一段相对于前一段只有上下左右四种状态，仅需要两位表示，则尾巴状态最多需要7×2=14位二进制数表示，则我们可以构建矩阵pMatrix[21][21][16384]来保存访问过的状态，以避免重复访问相同的状态，后面的工作就是传统的宽搜过程了；
2、如果仅按上面的方法来做的话会超时，于是加入了下面的减枝优化。即先不考虑蛇尾，使用宽搜算出仅蛇头一段从初始点走到结束点所需要的最少步数minstep,然后将蛇尾的初始位置看作石块，再用宽搜算出仅蛇头从初始点走到结束点所需要的最少步数maxstep,这里可以证明所要求的最小步数就在区间[minstep,maxstep]内，如果minstep==maxstep，则该值就是所求值，如果minstep不存在（不可达），则所求蛇的路径也不存在，（这里有一点要说明的是，即使maxstep不存在，也不能说明所求最短路径不存在，因为求maxstep时将蛇尾看作固定的障碍物，而实际情况下，蛇尾会随蛇头运动，会使求maxstep过程中不可行的路径变为可行。）否则，我们就执行1里定义的宽搜过程，在宽搜过程中，当已走的步数加上从当前点到终点的最短距离（x坐标+y坐标）大于maxstep时，就不再考虑此路径，如此达到减枝提速的目的。
3、maxstep是上限可以这么理解：当将尾巴看作固定的障碍时，从头到终点要绕过尾巴，而实际情况下，尾巴随头移动，故要绕开尾巴所要走的步数<=固定尾巴时的情况，又只有在初始情况下，尾巴可能会出现在头所要走的路径的前方，需要绕开，在第一次绕开之后，尾巴就一直跟在头后面了，不会再成为障碍物，与没尾巴时的情况一样，因此maxstep即是步数的上限。

但还是TLE，估计是STL队列效率低的原因

#include <iostream>

#include <string.h>

#include <string>

#include <cmath>

#include <queue>

#define INF 1999999999

using namespace std;

struct SNote

{

int len;

int SnakeX[8];//蛇结点和位置 0号是头

int SnakeY[8];

int spa;

int deepth;

};

struct poi

{

int x;

int y;

int deepth;

}P;

int MAXss;

int MINss;

int Map[22][22];

int vis[21][21][16400];

queue<SNote> q;

int tovis(SNote sn)

{

string msg;

for(int i=0;i<sn.len-1;i++)

{

if(sn.SnakeX+1==sn.SnakeX[i+1]&&sn.SnakeY==sn.SnakeY[i+1])// shang

{

msg+="10";

}

else if(sn.SnakeX-1==sn.SnakeX[i+1]&&sn.SnakeY==sn.SnakeY[i+1])//xia

{

msg+="11";

}

else if(sn.SnakeY-1==sn.SnakeY[i+1]&&sn.SnakeX==sn.SnakeX[i+1])//zuo

{

msg+="00";

}

else if(sn.SnakeY+1==sn.SnakeY[i+1]&&sn.SnakeX==sn.SnakeX[i+1])//you

{

msg+="01";

}

// cout<<msg<<endl;

int sum=0;

for(int i=0;i<msg.length();i++)

{

if(msg=='1')

sum+=pow(2,i);

}

if(vis[sn.SnakeX[0]][sn.SnakeY[0]][sum]==0)

{

vis[sn.SnakeX[0]][sn.SnakeY[0]][sum]=1;

return 1;

}

else return 0;

}

int _bfs()

{

SNote b;

while(!q.empty())

{

b=q.front();

q.pop();

int m[22][22];

for(int i=0;i<22;i++)

for(int j=0;j<22;j++)

m[j]=Map[j];

SNote a=b;

for(int i=0;i<a.len;i++)

{

if(i==0)

m[b.SnakeX][b.SnakeY]=3;

else

m[b.SnakeX][b.SnakeY]=2;

}

if(m[1][1]==3)

{

return b.deepth;

}

else

{

//go up

a=b;

if(m[a.SnakeX[0]-1][a.SnakeY[0]]==0&&(a.deepth+a.SnakeX[0]-1+a.SnakeY[0]-2)<=MAXss)

{

int ac,bc;

ac=a.SnakeX[0]; bc=a.SnakeY[0];

for(int i=1;i<a.len;i++)

{

swap(ac,a.SnakeX);

swap(bc,a.SnakeY);

}

a.SnakeX[0]=a.SnakeX[0]-1;

if(tovis(a))

{

// cout<<"可以向up移动"<<endl;

a.deepth=b.deepth+1;

q.push(a);

}

else ;

}

//go down

a=b;

if(m[a.SnakeX[0]+1][a.SnakeY[0]]==0&&(a.deepth+a.SnakeX[0]+1+a.SnakeY[0]-2)<=MAXss)

{

int ac,bc;

ac=a.SnakeX[0]; bc=a.SnakeY[0];

for(int i=1;i<a.len;i++)

{

swap(ac,a.SnakeX);

swap(bc,a.SnakeY);

}

a.SnakeX[0]=a.SnakeX[0]+1;

if(tovis(a))

{

// cout<<"可以向down移动"<<endl;

a.deepth=b.deepth+1;

q.push(a);

}

else ;

}

//go right

a=b;

if(m[a.SnakeX[0]][a.SnakeY[0]+1]==0&&(a.deepth+a.SnakeX[0]+a.SnakeY[0]-1)<=MAXss)

{

int ac,bc;

ac=a.SnakeX[0]; bc=a.SnakeY[0];

for(int i=1;i<a.len;i++)

{

swap(ac,a.SnakeX);

swap(bc,a.SnakeY);

}

a.SnakeY[0]=a.SnakeY[0]+1;

if(tovis(a))

{

// cout<<"可以向right移动"<<endl;

a.deepth=b.deepth+1;

q.push(a);

}

else ;

}

//go left

a=b;

if(m[a.SnakeX[0]][a.SnakeY[0]-1]==0&&(a.deepth+a.SnakeX[0]+a.SnakeY[0]-3)<=MAXss)

{

int ac,bc;

ac=a.SnakeX[0]; bc=a.SnakeY[0];

for(int i=1;i<a.len;i++)

{

swap(ac,a.SnakeX);

swap(bc,a.SnakeY);

}

a.SnakeY[0]=a.SnakeY[0]-1;

if(tovis(a))

{

// cout<<"可以向left移动"<<endl;

a.deepth=b.deepth+1;

q.push(a);

}

else ;

}

return -1;

}

int _bfsMAX(SNote &sn)

{

int MMMp[22][22];

int vivis[22][22];

for(int i=0;i<22;i++)

{

for(int j=0;j<22;j++)

vivis[j]=MMMp[j]=Map[j];

}

for(int i=1;i<sn.len;i++)

{

MMMp[sn.SnakeX][sn.SnakeY]=1;

vivis[sn.SnakeX][sn.SnakeY]=1;

}

P.x=sn.SnakeX[0]; P.y=sn.SnakeY[0];

P.deepth=0;

queue<poi> qt;

qt.push(P);

while(!qt.empty())

{

poi K,L;

L=K=qt.front();

qt.pop();

if(K.x==1&&K.y==1)

{

return K.deepth;

}

else

{

K=L;

// go up

if(MMMp[K.x-1][K.y]==0&&vivis[K.x-1][K.y]==0)

{

//cout<<"let's go up\n";

K.x=K.x-1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go down

if(MMMp[K.x+1][K.y]==0&&vivis[K.x+1][K.y]==0)

{

//cout<<"let's go down\n";

K.x=K.x+1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go left

if(MMMp[K.x][K.y-1]==0&&vivis[K.x][K.y-1]==0)

{

K.y=K.y-1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go right

if(MMMp[K.x][K.y+1]==0&&vivis[K.x][K.y+1]==0)

{

K.y=K.y+1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

return INF;

}

int _bfsNIN(SNote &sn)

{

int MMMp[22][22];

int vivis[22][22];

for(int i=0;i<22;i++)

{

for(int j=0;j<22;j++)

vivis[j]=MMMp[j]=Map[j];

}

P.x=sn.SnakeX[0]; P.y=sn.SnakeY[0];

P.deepth=0;

queue<poi> qt;

qt.push(P);

while(!qt.empty())

{

poi K,L;

L=K=qt.front();

qt.pop();

if(K.x==1&&K.y==1)

{

return K.deepth;

}

else

{

K=L;

// go up

if(MMMp[K.x-1][K.y]==0&&vivis[K.x-1][K.y]==0)

{

//cout<<"let's go up\n";

K.x=K.x-1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go down

if(MMMp[K.x+1][K.y]==0&&vivis[K.x+1][K.y]==0)

{

//cout<<"let's go down\n";

K.x=K.x+1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go left

if(MMMp[K.x][K.y-1]==0&&vivis[K.x][K.y-1]==0)

{

K.y=K.y-1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

K=L;

//go right

if(MMMp[K.x][K.y+1]==0&&vivis[K.x][K.y+1]==0)

{

K.y=K.y+1;

vivis[K.x][K.y]=1;

K.deepth=K.deepth+1;

qt.push(K);

}

return INF;

}

int main()

{

int tot=0;

int m,n,c;

while(cin>>n>>m>>c&&m!=0&&c!=0&&n!=0)

{

SNote sn;

tot++;

memset(Map,0,sizeof(Map));

memset(vis,0,sizeof(vis));

for(int i=0;i<=m+1;i++)

{

Map[0]=1;

Map[n+1]=1;

}

for(int i=0;i<=n+1;i++)

{

Map[0]=1;

Map[m+1]=1;

}

sn.len=c;

for(int i=0;i<c;i++)

{

cin>>sn.SnakeX>>sn.SnakeY;

}

sn.deepth=0;

int k;

cin>>k;

for(int i=0;i<k;i++)

{

int a,b;

cin>>a>>b;

Map[a]=1;

}

q.push(sn);

MAXss=_bfsMAX(sn);

MINss=_bfsNIN(sn);

// cout<<MAXss<<endl;

if(MINss==MAXss) cout<<"Case "<<tot<<": "<<MINss<<endl;

else if(MINss==INF) cout<<"Case "<<tot<<": "<<-1<<endl;

else

cout<<"Case "<<tot<<": "<<_bfs()<<endl;

while(!q.empty())

q.pop();

}

return 0;

}

贴一个可以AC的：（想抄的就去抄吧）

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 2005

#define inf 1<<28

using namespace std;

int n,m,k;

struct snake

{

int x,y;

} Snake[10],q1[1000000];//记录贪食蛇的坐标

int ans=-1;

struct snakeState

{

snake body[8];

int num;

} q[1000000];//一整条蛇和蛇走的路程

bool Map[21][21];

bool visit[21][21][17000];

int movex[4]= {0,1,0,-1}; //l,d,r,u

int movey[4]= {-1,0,1,0};

bool visit1[21][21];

int move[21][21];

int inmap(snake &x,snake body[])//判断是否可以走这步

{

if(x.x<=0||x.y<=0||x.x>n||x.y>m||Map[x.x][x.y])

return 0;

for(int i=1; i<k; i++)//蛇头与蛇身相撞，则不可以走

if(x.x==body.x&&x.y==body.y)

return 0;

for(int i=k-1; i>0; i--)//如果可以走这步将贪食蛇的位置更新

body=body[i-1];

body[0].x=x.x;//贪食蛇蛇头的新坐标

body[0].y=x.y;

return 1;//返回成功

}

int findmove(snake &a,snake &b)//找出从位置b-a是哪个方向过来的

{

if(a.x==b.x)

{

if(a.y<b.y)

return 0;//返回值与movex,movey的值要匹配

else return 1;

}

else

{

if(a.x>b.x)

return 3;

else return 2;

}

void bfs()

{

int i,j;

snakeState a;

for(i=0; i<k; i++)

a.body=Snake;

int num=0,cnt=0;

a.num=0;

int state=0;

for(i=0; i<k-1; i++)

state=4*state+findmove(Snake,Snake[i+1]);//计算贪食蛇的状态（唯一性）根据前一状态走到后一状态的方向计算得出

visit[Snake[0].x][Snake[0].y][state]=1;

q[0]=a;

num++;

while(cnt<num)

{

snakeState temp=q[cnt];

cnt++;

if(temp.body[0].x==1&&temp.body[0].y==1)

{

ans=temp.num;

return ;

}

for(i=0; i<4; i++)

{

snakeState now=temp;

snake now1;

now1.x=temp.body[0].x+movex;

now1.y=temp.body[0].y+movey;

if(!inmap(now1,now.body))//是否可以走

continue;

now.num=temp.num+1;

state=0;

for(j=0; j<k-1; j++)

state=4*state+findmove(now.body[j],now.body[j+1]);//计算当前的状态

if(visit[now.body[0].x][now.body[0].y][state])

continue;

visit[now.body[0].x][now.body[0].y][state]=1;

if(now.body[0].x==1&&now.body[0].y==1)

{

ans=now.num;

return ;

}

q[num]=now;

num++;

}

void bfs1()//计算min和max

{

int num=0,cnt=0;

q1[num]=Snake[0];

num++;

visit1[Snake[0].x][Snake[0].y]=1;

move[Snake[0].x][Snake[0].y]=1;

while(cnt<num)

{

snake temp=q1[cnt];

cnt++;

if(temp.x==1&&temp.y==1)

{

return ;

}

for(int i=0; i<4; i++)

{

int tx=temp.x+movex;

int ty=temp.y+movey;

if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&!visit1[tx][ty])

{

move[tx][ty]=move[temp.x][temp.y]+1;

if(tx==1&&ty==1)

return ;

visit1[tx][ty]=1;

snake now;

now.x=tx;

now.y=ty;

q1[num]=now;

num++;

}

void show()

{

int i,j;

for(i=1; i<=n; i++)

{

for(j=1; j<=m; j++)

cout<<move[j]<<" ";

cout<<endl;

}

int main()

{

int i,j,l,CASE=0;

while(scanf("%d%d%d",&n,&m,&k),n|m|k)

{

memset(Map,0,sizeof(Map));

memset(visit,0,sizeof(visit));

memset(visit1,0,sizeof(visit1));

memset(move,0,sizeof(move));

for(i=0; i<k; i++)

{

scanf("%d%d",&Snake.x,&Snake.y);

}

int kkk,x,y;

ans=-1;

//show();

scanf("%d",&kkk);

while(kkk--)

{

scanf("%d%d",&x,&y);

Map[x][y]=1;

visit1[x][y]=1;

}

bfs1();//第一次BFS只考虑蛇头和stone;

//show();

if(move[1][1]==0)//如果（1，1）不可到达

{

printf("Case %d: -1\n",++CASE);

continue;

}

int min=move[1][1];

memset(move,0,sizeof(move));

for(i=1; i<=n; i++)

{

for(j=1; j<=m; j++)

visit1[j]=Map[j];

}

for(i=1; i<k; i++)//第二次BFS，还要另外将蛇身看成stone

visit1[Snake.x][Snake.y]=1;

bfs1();

int max=move[1][1];

if(min==max)//如果 min和max相等

{

printf("Case %d: %d\n",++CASE,min-1);

continue;

}

bfs();

printf("Case %d: %d\n",++CASE,ans);

}

return 0;

}