山东2011省选第二轮第二试

《山东2011省选第二轮第二试》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011年全国青少年信息学奥林匹克山东省省队选拔赛（第二轮）第二试竞赛时间：2011年4月17日上午8:00—12:00题目名称贪食蛇保密消耗战目录snaketfnhnsmrepair可执行文件名snake.exetfnhnsm.exerepair.exe输入文件名snake.intfnhnsm.inrepair.in输出文件名snake.outtfnhnsm.outrepair.out每个测试点时限1s1s2s测试点数目201010每个测试点分值51010内存限制512MB512MB512MB是否有部分分无无无题目类型传统型传统型传统型提交源程序须加后缀对于

2、Pascal语言paspaspas对于C语言ccc对于C++语言cppcppcpp注意：最终测试时，所有编译命令均不打开任何优化开关。贪食蛇（snake）【问题描述】相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。活动区域：贪食蛇的活动区域是一个R行C列的网格A，贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个整数权值，记作w(Aij)。0<=w(Aij)<=8，w(Aij)=0时，Aij禁止进入；w(Aij)>0时，Aij

3、允许进入。方向：对于P=(X0,Y0)、Q=(X1,Y1)，有以下四种基本方向：l正左(L)：X0=X1且Y0=Y1-1，则称P位于Q的正左方向。l正右(R)：X0=X1且Y0=Y1+1，则称P位于Q的正右方向。l正上(U)：X0=X1-1且Y0=Y1，则称P位于Q的正上方向。l正下(D)：X0=X1+1且Y0=Y1，则称P位于Q的正下方向。贪食蛇：贪食蛇B是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为m，则贪食蛇从头到尾，用B1、B2、……、Bm表示。记p为贪食蛇的形态，若Bi位于第Xi行第Yi列，则p(Bi)=(Xi,Yi)。初始情况下，m=4，且

4、运动过程中始终需要满足以下限制：l对于Bi和Bi+1(1<=i

5、头部位于Aij上。记p’为贪食蛇新的形态，则：lp’(Bk)=p(Bk-1)，当2<=k<=m。lp’(Bk)=(i,j)，当k=1贪食蛇的进食：如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上存在食物，则贪食蛇可以向该方向进食，新的头部位于Aij上，蛇的新长度m’=m+1。记p’为贪食蛇新的位置，则：lp’(Bk)=p(Bk-1)，当2<=k<=m’。lp’(Bk)=(i,j)，当k=1注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置

6、，因为在变换后头部和尾部仍不会重叠。运动或进食所需要的时间：贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是Q，则此次运动或进食的所消耗的时间为

7、w(P)-w(Q)

8、+1。游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。【输入格式】第一行，两个正整数R、C。接下来R行，每行C个没有空格分隔的数字。其中第i行第j个数字为w(Aij)。接下来4行，每行2个正整数。第i行的两个整数Xi、Yi，表示p(Bi)=(Xi,Yi)。接下来一个正整数N，表示食物的数量。接下来N行

9、，每行2个正整数i、j，表示Aij上存在一个食物。【输出格式】如果贪食蛇不能吃到所有的食物，输出“Nosolution.”（不包括引号）。否则，输出：第一行，一个整数，表示所需花费的时间；第二行，一个由L、R、U、D组成的字符串，表示贪食蛇前进的方案。如果存在多种可能，你只需输出任意一种。【样例输入】55110111101111011110111141111213141455442514【样例输出】21RDDDDRRRULURULU【数据规模和约定】对于20%的数据，N<=1。对于40%的数据，N<=2。对于60%的数据，N<=3。对于100%的数据，N<=4

10、。对于30%的数据，R*C<=36。对