#BZOJ2284. 贪食蛇
-
ID: 722
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
贪食蛇
No submission language available for this problem.
题目描述
相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。
活动区域：
贪食蛇的活动区域是一个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 正左(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，且运动过程中始终需要满足以下限制：
l 对于Bi和Bi+1(1<=i<m)，就是贪食蛇的前、后相邻两部分，必须满足Bi位于Bi+1的L、R、U、D四个方向之一。
l 对于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’为贪食蛇新的形态，则：
l p’(Bk)=p(Bk-1)，当2<=k<=m。
l p’(Bk)=(i,j)，当k=1
贪食蛇的进食：
如果贪食蛇的头部B1的L、R、U、D四个方向之一的Aij能进入，且Aij上存在食物，则贪食蛇可以向该方向进食，新的头部位于Aij上，蛇的新长度m’=m+1。记p’为贪食蛇新的位置，则：
l p’(Bk)=p(Bk-1)，当2<=k<=m’。
l 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.”（不包括引号）。
否则，输出：
第一行，一个整数，表示所需花费的时间；
5 5
11011
11011
11011
11011
11411
1 1
2 1
3 1
4 1
4
5 5
4 4
2 5
1 4
【样例输出】
21
数据范围与约定
对于20%的数据，N <= 1。
对于40%的数据，N <= 2。
对于60%的数据，N <= 3。
对于100%的数据，N <= 4。
对于30%的数据，R * C <= 36。
对于100%的数据，R <= 12，C <= 12。