Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解
Description
题目链接Luogu 题目链接bzoj
相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。
活动区域：
贪食蛇的活动区域是一个R行C列的网格A，贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个整数权值，记作w(Aij)。0<=w(Aij)<=8，w(Aij)=0时，Aij禁止进入；w(Aij)>0时，Aij允许进入。
方向：
对于P=(X0,Y0)、Q=(X1,Y1)，有以下四种基本方向：
- 正左(L)：X0=X1且Y0=Y1-1，则称P位于Q的正左方向。
- 正右(R)：X0=X1且Y0=Y1 1，则称P位于Q的正右方向。
- 正上(U)：X0=X1-1且Y0=Y1，则称P位于Q的正上方向。
- 正下(D)：X0=X1 1且Y0=Y1，则称P位于Q的正下方向。
贪食蛇：
贪食蛇B是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为m，则贪食蛇从头到尾，用B1、B2、……、Bm表示。记p为贪食蛇的形态，若Bi位于第Xi行第Yi列，则p(Bi)=(Xi,Yi)。初始情况下，m=4，且运动过程中始终需要满足以下限制：
- 对于Bi和Bi 1(1<=i<m)，就是贪食蛇的前、后相邻两部分，必须满足Bi位于Bi 1的L、R、U、D四个方向之一。
- 对于Bi和Bj(1<=i<j<=m)，p(Bi)=(Xi,Yi)，p(Bj)=(Xj,Yj)，需要满足Xi!=Xj或Yi!=Yj。也就是说，贪食蛇身体的任意一部分不能相交。
食物：
贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。
贪食蛇的运动：
如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上不存在食物，则贪食蛇可以向该方向运动，新的头部位于Aij上。记p’为贪食蛇新的形态，则：
- p’(Bk)=p(Bk-1)，当2<=k<=m。
- p’(Bk)=(i,j)，当k=1
贪食蛇的进食：
如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上存在食物，则贪食蛇可以向该方向进食，新的头部位于Aij上，蛇的新长度m’=m 1。记p’为贪食蛇新的位置，则：
- p’(Bk)=p(Bk-1)，当2<=k<=m’。
- p’(Bk)=(i,j)，当k=1
注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。
运动或进食所需要的时间：
贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是Q，则此次运动或进食的所消耗的时间为w(P)-w(Q) 1。
游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。
Solution
一句话题意：初始时有一条长度为4的贪吃蛇，每走一步需要时间为两格权值之差的绝对值，问最少的时间令贪吃蛇吃完所有的食物。
其中，食物数量leq 4，矩阵长宽均leq 15。
Code
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();while(isdigit(ch)) res=(res<<3) (res<<1) (ch&15),ch=getchar();return res*f;}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x '0');else write(x/10),putchar(x '0');}
const int dx[]={0,0,-1,1},
dy[]={-1,1,0,0};
const char W[]={'L','R','U','D'};
int n,m,w[17][17],snk[5][2],fd,g[17][17],HH,TT,S[1<<11][4],T[1<<11][4],Q[255*1200*16*8],pre[255*1200*16*8],Ans,AnsT,AnsN;
char c,AnsP[17*17];
unsigned long long vis[1<<23];
inline int abs(int x){return x<0?-x:x;}
inline void init(){
n=read(),m=read();
c=getchar();for(int i=1;i<=n;i ){
while(!isdigit(c)) c=getchar();
for(int j=1;j<=m;j ) w[i][j]=c-'0',c=getchar();
}
for(int i=1;i<=4;i )
for(int j=0;j<=1;j ) snk[i][j]=read();
fd=read();
for(int x,y,i=1;i<=fd;i ) x=read(),y=read(),g[x][y]=i;
}
inline int get(int s,int len,int t){
len =4;t^=1;
int x=dx[t],y=dy[t];
for(int j=s,i=2;i<len;i ,j>>=2){
x =dx[j&3],y =dy[j&3];
if(!x&&!y) return -1;
}
return (s<<2&((1<<((len-1)<<1))-1))t;
}
inline int pos(int x,int y,int xx,int yy){
for(int i=0;i<4;i )
if(x dx[i]==xx&&y dy[i]==yy) return i;
}
inline void load(){
memset(S,0xFF,sizeof(S));
memset(T,0xFF,sizeof(T));
memset(vis,0,sizeof(vis));
HH=TT=0;
int s=0;
for(int i=4;i>=2;i--)
s=(s<<2)pos(snk[i-1][0],snk[i-1][1],snk[i][0],snk[i][1]);
s<<=2;vis[s]= TT;Q[TT]=s;
while(HH<TT){
int u=Q[ HH];
int del=u>>2,len=u&3;
for(int i=0;i<4;i ){
int nxt=get(del,len,i);
if(nxt<0) continue ;
int s=(nxt&((1<<12)-1))<<2len;
if(!vis[s]) Q[ TT]=s,vis[s]=TT;
S[HH][i]=vis[s];
}
for(int i=0;i<4;i ){
int nxt=get(del,len 1,i);
if(nxt<0) continue ;
if(len<3){
int s=(nxt&((1<<12)-1))<<2(len 1);
if(!vis[s]) Q[ TT]=s,vis[s]=TT;
T[HH][i]=vis[s];
}else T[HH][i]=0;
}
}
}
#define make_S(x,y,ss,tt,wt) ((x)<<22((y)<<18)(ss<<7)((tt)<<3)(wt))
#define check(s,wt) (vis[(s)>>3]&1<<(wt))
inline void bfs(){
memset(vis,0,sizeof(vis));
HH=TT=0;
Q[ TT]=make_S(snk[1][0],snk[1][1],1,(1<<fd)-1,0);
vis[Q[TT]>>3]=1;
while(HH<TT){
int u=Q[ HH];
int x=u>>22&((1<<4)-1),y=u>>18&((1<<4)-1),sq=u>>7&((1<<11)-1),t=u>>3&((1<<4)-1),wt=u&((1<<3)-1);
if(!t&&!wt){Ans=HH;break ;}
if(wt){
int s=make_S(x,y,sq,t,wt-1);
if(!check(s,wt-1)) Q[ TT]=s,vis[s>>3]=1<<(wt-1),pre[TT]=HH;
}else{
for(int i=0;i<4;i ){
int xx=x dx[i],yy=y dy[i],ns=S[sq][i],nt=t,nwt=abs(w[xx][yy]-w[x][y]);
if(!w[xx][yy]) continue ;
if(g[xx][yy]&&t&1<<(g[xx][yy]-1)) ns=T[sq][i],nt^=1<<(g[xx][yy]-1);
else ns=S[sq][i];
if(ns<0) continue ;
int s=make_S(xx,yy,ns,nt,nwt);
if(!check(s,nwt))
Q[ TT]=s,
vis[s>>3]=1<<nwt,
pre[TT]=HH;
}
}
}
}
inline void solve(){
for(int p=Ans;p>1;p=pre[p]){
AnsT;
int wt=Q[pre[p]]&((1<<3)-1);
if(wt) continue ;
int x=Q[pre[p]]>>22&((1<<4)-1),y=Q[pre[p]]>>18&((1<<4)-1),xx=Q[p]>>22&((1<<4)-1),yy=Q[p]>>18&((1<<4)-1);
AnsP[AnsN ]=W[pos(x,y,xx,yy)];
}
for(int i=0;i<(AnsN>>1);i ) swap(AnsP[i],AnsP[AnsN-i-1]);
}
inline void print(){
if(!Ans){
puts("No solution.");
return ;
}
write(AnsT);putchar('n');
for(int i=0;i<AnsN;i ) putchar(AnsP[i]);putchar('n');
}
int main(){return init(),load(),bfs(),solve(),print(),0;}
