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

暂无评论

发送评论 编辑评论


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