P2493 [SDOI2011]贪食蛇

    • 7通过
    • 62提交
  • 题目提供者 a320831
  • 评测方式 云端评测
  • 标签 各省省选 2011 山东
  • 难度 提高+/省选-
  • 时空限制 500ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    相信大家都玩过贪食蛇游戏,现在有一个改版贪食蛇游戏,跟传统的贪食蛇游戏一样,贪食蛇在活动区域内运动,吃食物,但是这个改版的贪食蛇游戏有着一些特别的规则。

    活动区域:

    贪食蛇的活动区域是一个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。

    游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是,以最少的时间令贪食蛇吃完所有食物。

    输入输出格式

    输入格式:

    第一行,两个正整数R、C。

    接下来R行,每行C个没有空格分隔的数字。其中第i行第j个数字为w(Aij)。

    接下来4行,每行2个正整数。第i行的两个整数Xi、Yi,表示p(Bi)=(Xi,Yi)。

    接下来一个正整数N,表示食物的数量。

    接下来N行,每行2个正整数i、j,表示Aij上存在一个食物。

    输出格式:

    如果贪食蛇不能吃到所有的食物,输出“No solution.”(不包括引号)。

    否则,输出:

    第一行,一个整数,表示所需花费的时间;

    第二行,一个由L、R、U、D组成的字符串,表示贪食蛇前进的方案。如果存在多种可能,你只需输出任意一种。

    输入输出样例

    输入样例#1: 复制
    5 5
    11011
    11011
    11011
    11011
    11411
    1 1
    2 1
    3 1
    4 1
    4
    5 5
    4 4
    2 5
    1 4
    输出样例#1: 复制
    21
    RDDDDRRRULURULU
    

    说明

    【数据规模和约定】

    对于20%的数据,N <= 1。

    对于40%的数据,N <= 2。

    对于60%的数据,N <= 3。

    对于100%的数据,N <= 4。

    对于30%的数据,R * C <= 36。

    对于100%的数据,R <= 12,C <= 12。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。