题意:给出蛇头和蛇身(蛇身分为若干节,用坐标连起来,当然蛇头也是一个坐标)
给出终点坐标,障碍物坐标,问蛇能不能到达终点(蛇头到达)
本题可以用状态压缩,表示蛇头在x,y,蛇身的状态。蛇身的状态可以用该部分和上一部分的相对位置来表示,分别有四种状态就是在它的上下左右,分别记为0,1,2,3,二进制位是00,01,10,11。蛇身长共7节,7*2也就是14位,空间足够,然后一节一节广搜就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<bitset>
using std::bitset;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct edge {
int st,x[10],y[10],sta;
bitset<23> d[23];
edge (){
st=sta=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
}
};
int map[24][24];
int n,m,l,k,v[22][22][1<<15];
int ch[5][5];
inline int check(edge now,int x,int y){
int sta=0;
for(int i=2;i<=l;++i){
int temp=0;
temp=ch[now.x[i]-now.x[i-1]+1][now.y[i]-now.y[i-1]+1];
sta|=temp<<((i-1)*2);
}
if(v[x][y][sta]) return 0;
v[x][y][sta]=1;
return 1;
}
inline edge copy(edge old,int x,int y){
edge nwe;
for(int i=2;i<=l;++i){
nwe.x[i]=old.x[i-1];
nwe.y[i]=old.y[i-1];
}
for(int i=1;i<=n;++i) nwe.d[i]=old.d[i];
nwe.st=old.st+1;
nwe.d[old.x[l]][old.y[l]]=0;
nwe.x[1]=x,nwe.y[1]=y;
nwe.d[x][y]=1;
return nwe;
}
inline int BFS(edge star){
std::queue<edge> q;
while(!q.empty()) q.pop();
q.push(star);
while(!q.empty()){
edge now=q.front();q.pop();
if(now.x[1]==1&&now.y[1]==1) return now.st;
for(int i=0;i<=3;++i){
int gx=dx[i]+now.x[1];
int gy=dy[i]+now.y[1];
if(now.d[gx][gy]==1) continue;
if(gx<=0||gy<=0||gx>n||gy>m) continue;
if(check(now,gx,gy)){
edge nwe=copy(now,gx,gy);
if(gx==1&&gy==1) return nwe.st;
q.push(nwe);
}
}
}
return 0x3f3f3f3f;
}
int main (){
int T=0;
ch[-1+1][0+1]=1;
ch[1+1][0+1]=2;
ch[0+1][1+1]=4;
ch[0+1][-1+1]=4;
while(scanf("%d %d %d",&n,&m,&l)){
T++;
memset(v,0,sizeof(v));
memset(map,0,sizeof(map));
if(n==0&m==0&l==0) return 0;
edge st;
for(int j=1;j<=l;++j)
for(int i=1;i<=l;++i)
st.d[i][j]=0;
for(int i=1;i<=l;++i){
int x,y,z=0;
scanf("%d %d",&x,&y);
st.d[x][y]=1;
st.x[i]=x,st.y[i]=y;
if(i!=1)
z=ch[st.x[i]-st.x[i-1]+1][st.y[i]-st.y[i-1]+1];
st.sta|=z<<((i-1)*2);
}
v[st.x[1]][st.y[1]][st.sta]=1;
scanf("%d",&k);
while(k--){
int x,y;
scanf("%d %d",&x,&y);
st.d[x][y]=1;
map[x][y]=1;
}
int ans=BFS(st);
if(ans!=0x3f3f3f3f){
printf("Case %d: %d\n",T,ans);
}
else{
printf("Case %d: %d\n",T,-1);
}
}
return 0;
}
0 条评论