#2284. [Sdoi2011]贪食蛇

题目描述

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

活动区域：

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