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

#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))<<2|len;
			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;}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇