题目描述
相信大家都玩过贪食蛇游戏,现在有一个改版贪食蛇游戏,跟传统的贪食蛇游戏一样,贪食蛇在活动区域内运动,吃食物,但是这个改版的贪食蛇游戏有着一些特别的规则。
活动区域:
贪食蛇的活动区域是一个 R 行 C 列的网格 A,贪食蛇活动不能超过这个网格的范围。第 i 行第 j 列的方格用 Ai,j 表示。每个方格有一个整数权值,记作 w(Ai,j)。0≤w(Ai,j)≤8,w(Ai,j)=0时,Ai,j 禁止进入;w(Ai,j)>0时,Ai,j 允许进入。
方向:
对于 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<m),就是贪食蛇的前、后相邻两部分,必须满足 Bi 位于 Bi+1 的L、R、U、D四个方向之一。
- 对于 Bi 和 Bj (1≤i<j≤m),p(Bi)=(Xi,Yi),p(Bj)=(Xj,Yj),需要满足 Xi=Xj 或 Yi=Yj 。也就是说,贪食蛇身体的任意一部分不能相交。
食物:
贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上,食物不会重叠。每个食物只能被吃一次。
贪食蛇的运动:
如果贪食蛇的头部 B1 的L、R、U、D四个方向之一的 Ai,j 能进入,且 Ai,j 上不存在食物,则贪食蛇可以向该方向运动,新的头部位于 Ai,j 上。记 p′ 为贪食蛇新的形态,则:
- p′(Bk)=p(Bk−1),当 2≤k≤m。
- p′(Bk)=(i,j),当 k=1。
贪食蛇的进食:
如果贪食蛇的头部 B1 的L、R、U、D四个方向之一的 Ai,j 能进入,且 Ai,j 上存在食物,则贪食蛇可以向该方向进食,新的头部位于 Ai,j 上,蛇的新长度 m′=m+1。记 p′ 为贪食蛇新的位置,则:
- p′(Bk)=p(Bk−1),当 2≤k≤m′。
- p′(Bk)=(i,j),当 k=1.
注意:运动或进食后的贪食蛇形态,仅仅需要考虑变换后的形态是否满足限制,不需要考虑变换的过程。也就是说,原来形态合法的贪食蛇的头部可以运动到尾部的位置,因为在变换后头部和尾部仍不会重叠。
运动或进食所需要的时间:
贪食蛇运动或进食,需要消耗时间。设运动或进食前头部所在的方格是P,运动或进食后头部所在的方格是 Q,则此次运动或进食的所消耗的时间为 ∣w(P)−w(Q)∣+1。
游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是,以最少的时间令贪食蛇吃完所有食物。
输入格式
第一行,两个正整数 R,C。
接下来 R 行,每行 C 个没有空格分隔的数字。其中第 i 行第 j 个数字为 w(Ai,j)。
接下来 4 行,每行 2 个正整数。第 i 行的两个整数 Xi,Yi,表示 p(Bi)=(Xi,Yi)。
接下来一个正整数 N,表示食物的数量。
接下来 N 行,每行 2 个正整数 i,j,表示 Ai,j上存在一个食物。
输出格式
如果贪食蛇不能吃到所有的食物,输出 No solution.
。
否则,输出:
第一行,一个整数,表示所需花费的时间;
第二行,一个由 L、R、U、D 组成的字符串,表示贪食蛇前进的方案。如果存在多种可能,你只需输出任意一种。
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
RDDDDRRRULURULU
提示
- 对于 20% 的数据,N≤1;
- 对于 30% 的数据,R×C≤36;
- 对于 40% 的数据,N≤2;
- 对于 60% 的数据,N≤3;
- 对于 100% 的数据,N≤4,R≤12,C≤12。