[SDOI2011] 贪食蛇

题目描述

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

输入输出格式

输入格式


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

输出格式


如果贪食蛇不能吃到所有的食物,输出 `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 \leq 1$; - 对于 $30\%$ 的数据,$R \times C \leq 36$; - 对于 $40\%$ 的数据,$N \leq 2$; - 对于 $60\%$ 的数据,$N \leq 3$; - 对于 $100\%$ 的数据,$N \leq 4$,$R \leq 12$,$C \leq 12$。