#2284. [Sdoi2011]贪食蛇

内存限制:512 MiB 时间限制:10 Sec

题目描述

 
 
 
相信大家都玩过贪食蛇游戏,现在有一个改版贪食蛇游戏,跟传统的贪食蛇游戏一样,贪食蛇在活动区域内运动,吃食物,但是这个改版的贪食蛇游戏有着一些特别的规则。
 
活动区域:
贪食蛇的活动区域是一个RC列的网格A,贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个整数权值,记作w(Aij)0<=w(Aij)<=8w(Aij)=0时,Aij禁止进入;w(Aij)>0时,Aij允许进入。
 
方向:
对于P=(X0,Y0)Q=(X1,Y1),有以下四种基本方向:
l        正左(L)X0=X1Y0=Y1-1,则称P位于Q的正左方向。
l        正右(R)X0=X1Y0=Y1+1,则称P位于Q的正右方向。
l        正上(U)X0=X1-1Y0=Y1,则称P位于Q的正上方向。
l        正下(D)X0=X1+1Y0=Y1,则称P位于Q的正下方向。
 
贪食蛇:
贪食蛇B是占据若干方格的图形,占据的方格数为贪食蛇的长度,记为m,则贪食蛇从头到尾,用B1B2……Bm表示。记p为贪食蛇的形态,若Bi位于第Xi行第Yi列,则p(Bi)=(Xi,Yi)。初始情况下,m=4,且运动过程中始终需要满足以下限制:
l        对于BiBi+1(1<=i<m),就是贪食蛇的前、后相邻两部分,必须满足Bi位于Bi+1LRUD四个方向之一。
l        对于BiBj(1<=i<j<=m)p(Bi)=(Xi,Yi)p(Bj)=(Xj,Yj),需要满足Xi!=XjYi!=Yj。也就是说,贪食蛇身体的任意一部分不能相交。
 
食物:
贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上,食物不会重叠。每个食物只能被吃一次。
 
贪食蛇的运动:
如果贪食蛇的头部B1LRUD四个方向之一的Aij能进入,且Aij上不存在食物,则贪食蛇可以向该方向运动,新的头部位于Aij上。记p’为贪食蛇新的形态,则:
l        p’(Bk)=p(Bk-1),当2<=k<=m
l        p’(Bk)=(i,j),当k=1
 
贪食蛇的进食:
如果贪食蛇的头部B1LRUD四个方向之一的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
 
游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是,以最少的时间令贪食蛇吃完所有食物。

输入格式

第一行,两个正整数RC
接下来R行,每行C个没有空格分隔的数字。其中第i行第j个数字为w(Aij)
接下来4行,每行2个正整数。第i行的两个整数XiYi,表示p(Bi)=(Xi,Yi)
接下来一个正整数N,表示食物的数量。
接下来N行,每行2个正整数ij,表示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。