[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):X0=X1且Y0=Y1-1,则称P位于Q的正左方向。  正右(R):X0=X1且Y0=Y1+1,则称P位于Q的正右方向。  正上(U):X0=X1-1且Y0=Y1,则称P位于Q的正上方向。  正下(D):X0=X1+1且Y0=Y1,则称P位于Q的正下方向。 贪食蛇: 贪食蛇B是占据若干方格的图形,占据的方格数为贪食蛇的长度,记为m,则贪食蛇从头到尾,用B1、B2、……、Bm表示。记p为贪食蛇的形态,若Bi位于第Xi行第Yi列,则p(Bi)=(Xi,Yi)。初始情况下,m=4,且运动过程中始终需要满足以下限制:  对于Bi和Bi+1(1<=i

输入输出格式

输入格式


第一行,两个正整数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.”(不包括引号)。 否则,输出: 第一行,一个整数,表示所需花费的时间; 第二行,一个由L、R、U、D组成的字符串,表示贪食蛇前进的方案。如果存在多种可能,你只需输出任意一种。

输入输出样例

输入样例 #1

5 5
11011
11011
11011
11011
11411
1 1
2 1
3 1
4 1
4
5 5
4 4
2 5
1 4

输出样例 #1

21
RDDDDRRRULURULU

说明

【数据规模和约定】 对于20%的数据,N <= 1。 对于40%的数据,N <= 2。 对于60%的数据,N <= 3。 对于100%的数据,N <= 4。 对于30%的数据,R \* C <= 36。 对于100%的数据,R <= 12,C <= 12。