6284: BZOJ2284：[Sdoi2011]贪食蛇

      相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。   活动区域： 贪食蛇的活动区域是一个R行C列的网格A，贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用A_i,j表示。每个方格有一个整数权值，记作w(A_ij)。0<=w(A_ij)<=8，w(A_ij)=0时，A_ij禁止进入；w(A_ij)>0时，A_ij允许进入。   方向： 对于P=(X₀,Y₀)、Q=(X₁,Y₁)，有以下四种基本方向： l        正左(L)：X₀=X₁且Y₀=Y₁-1，则称P位于Q的正左方向。 l        正右(R)：X₀=X₁且Y₀=Y₁+1，则称P位于Q的正右方向。 l        正上(U)：X₀=X₁-1且Y₀=Y₁，则称P位于Q的正上方向。 l        正下(D)：X₀=X₁+1且Y₀=Y₁，则称P位于Q的正下方向。   贪食蛇： 贪食蛇B是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为m，则贪食蛇从头到尾，用B₁、B₂、……、B_m表示。记p为贪食蛇的形态，若Bi位于第X_i行第Y_i列，则p(B_i)=(X_i,Y_i)。初始情况下，m=4，且运动过程中始终需要满足以下限制： l        对于B_i和B_i+1(1<=i<m)，就是贪食蛇的前、后相邻两部分，必须满足B_i位于B_i+1的L、R、U、D四个方向之一。 l        对于B_i和B_j(1<=i<j<=m)，p(B_i)=(X_i,Y_i)，p(B_j)=(X_j,Y_j)，需要满足X_i!=X_j或Y_i!=Y_j。也就是说，贪食蛇身体的任意一部分不能相交。   食物： 贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。   贪食蛇的运动： 如果贪食蛇的头部B₁的L、R、U、D四个方向之一的A_ij能进入，且A_ij上不存在食物，则贪食蛇可以向该方向运动，新的头部位于A_ij上。记p’为贪食蛇新的形态，则： l        p’(B_k)=p(B_k-1)，当2<=k<=m。 l        p’(B_k)=(i,j)，当k=1   贪食蛇的进食： 如果贪食蛇的头部B₁的L、R、U、D四个方向之一的A_ij能进入，且A_ij上存在食物，则贪食蛇可以向该方向进食，新的头部位于A_ij上，蛇的新长度m’=m+1。记p’为贪食蛇新的位置，则： l        p’(B_k)=p(B_k-1)，当2<=k<=m’。 l        p’(B_k)=(i,j)，当k=1   注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。   运动或进食所需要的时间： 贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是P，运动或进食后头部所在的方格是Q，则此次运动或进食的所消耗的时间为|w(P)-w(Q)|+1。   游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。

输入格式

第一行，两个正整数R、C。 接下来R行，每行C个没有空格分隔的数字。其中第i行第j个数字为w(A_ij)。 接下来4行，每行2个正整数。第i行的两个整数X_i、Y_i，表示p(B_i)=(X_i,Y_i)。 接下来一个正整数N，表示食物的数量。 接下来N行，每行2个正整数i、j，表示A_ij上存在一个食物。

输出格式

  如果贪食蛇不能吃到所有的食物，输出“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。

题目来源

Stage2 day2