Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解

(Updated: )
oi

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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%10+'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;}