#P2493. [SDOI2011] 贪食蛇

[SDOI2011] 贪食蛇

题目描述

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

活动区域:

贪食蛇的活动区域是一个 RRCC 列的网格 AA,贪食蛇活动不能超过这个网格的范围。第 ii 行第 jj 列的方格用 Ai,jA_{i,j} 表示。每个方格有一个整数权值,记作 w(Ai,j)w(A_{i,j})0w(Ai,j)80 \leq w(A_{i,j}) \leq 8w(Ai,j)=0w(A_{i,j}) = 0时,Ai,jA_{i,j} 禁止进入;w(Ai,j)>0w(A_{i, j}) > 0时,Ai,jA_{i, j} 允许进入。

方向:

对于 P=(X0,Y0)P = (X_0, Y_0)Q=(X1,Y1)Q = (X_1, Y_1),有以下四种基本方向:

  • 正左(L):X0=X1X_0 = X_1Y0=Y11Y_0 = Y_1 - 1,则称 PP 位于 QQ 的正左方向。
  • 正右(R):X0=X1X_0 = X_1Y0=Y1+1Y_0 = Y_1 + 1,则称 PP 位于 QQ 的正右方向。
  • 正上(U):X0=X11X_0 = X_1 - 1Y0=Y1Y_0 = Y_1,则称 PP 位于 QQ 的正上方向。
  • 正下(D):X0=X1+1X_0 = X_1 + 1Y0=Y1Y_0 = Y_1,则称 PP 位于 QQ 的正下方向。

贪食蛇:

贪食蛇 BB 是占据若干方格的图形,占据的方格数为贪食蛇的长度,记为 mm,则贪食蛇从头到尾,用 B1,B2,,BmB_1, B_2, \dots, B_m表示。记 pp 为贪食蛇的形态,若 BiB_i 位于第 XiX_i 行第 YiY_i 列,则 p(Bi)=(Xi,Yi)p(B_i)=(X_i, Y_i)。初始情况下,m=4m = 4,且运动过程中始终需要满足以下限制:

  • 对于 BiB_iBi+1B_{i + 1} (1i<m)(1 \leq i < m),就是贪食蛇的前、后相邻两部分,必须满足 BiB_i 位于 Bi+1B_{i + 1} 的L、R、U、D四个方向之一。
  • 对于 BiB_iBjB_j (1i<jm)(1 \leq i < j \leq m)p(Bi)=(Xi,Yi)p(B_i) = (X_i, Y_i)p(Bj)=(Xj,Yj)p(B_j) = (X_j,Y_j),需要满足 XiXjX_i \neq X_jYiYjY_i \neq Y_j 。也就是说,贪食蛇身体的任意一部分不能相交。

食物:

贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上,食物不会重叠。每个食物只能被吃一次。

贪食蛇的运动:

如果贪食蛇的头部 B1B1 的L、R、U、D四个方向之一的 Ai,jA_{i, j} 能进入,且 Ai,jA_{i, j} 上不存在食物,则贪食蛇可以向该方向运动,新的头部位于 Ai,jA_{i, j} 上。记 pp' 为贪食蛇新的形态,则:

  • p(Bk)=p(Bk1)p'(B_k) = p(B_{k - 1}),当 2km2 \leq k \leq m
  • p(Bk)=(i,j)p'(B_k) = (i, j),当 k=1k = 1

贪食蛇的进食:

如果贪食蛇的头部 B1B_1 的L、R、U、D四个方向之一的 Ai,jA_{i, j} 能进入,且 Ai,jA_{i,j} 上存在食物,则贪食蛇可以向该方向进食,新的头部位于 Ai,jA_{i, j} 上,蛇的新长度 m=m+1m'=m+1。记 pp' 为贪食蛇新的位置,则:

  • p(Bk)=p(Bk1)p'(B_k) = p(B_{k-1}),当 2km2 \leq k \leq m'
  • p(Bk)=(i,j)p'(B_k) = (i,j),当 k=1k = 1.

注意:运动或进食后的贪食蛇形态,仅仅需要考虑变换后的形态是否满足限制,不需要考虑变换的过程。也就是说,原来形态合法的贪食蛇的头部可以运动到尾部的位置,因为在变换后头部和尾部仍不会重叠。

运动或进食所需要的时间:

贪食蛇运动或进食,需要消耗时间。设运动或进食前头部所在的方格是P,运动或进食后头部所在的方格是 QQ,则此次运动或进食的所消耗的时间为 w(P)w(Q)+1|w(P) - w(Q)| + 1

游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是,以最少的时间令贪食蛇吃完所有食物。

输入格式

第一行,两个正整数 R,CR, C

接下来 RR 行,每行 CC 个没有空格分隔的数字。其中第 ii 行第 jj 个数字为 w(Ai,j)w(A_{i, j})

接下来 44 行,每行 22 个正整数。第 ii 行的两个整数 Xi,YiX_i, Y_i,表示 p(Bi)=(Xi,Yi)p(B_i) = (X_i, Y_i)

接下来一个正整数 NN,表示食物的数量。

接下来 NN 行,每行 22 个正整数 i,ji, j,表示 Ai,jA_{i, 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%20\% 的数据,N1N \leq 1
  • 对于 30%30\% 的数据,R×C36R \times C \leq 36
  • 对于 40%40\% 的数据,N2N \leq 2
  • 对于 60%60\% 的数据,N3N \leq 3
  • 对于 100%100\% 的数据,N4N \leq 4R12R \leq 12C12C \leq 12