题目描述

推箱子（Sokoban）是一款由今林博之（Hiroyuki Imabayashi）于 1981 年创作的益智视频游戏系列，玩家在仓库中推动箱子到指定的存储位置。尽管规则简单，推箱子展现出复杂而具有挑战性的行为，吸引了众多益智游戏爱好者和理论计算机科学家。1996 年，Dorit Dor 和 Uri Zwick 证明了推箱子是 NP 完全的，1997 年，Joseph C. Culberson 进一步证明了它是 PSPACE 完全的。至今，推箱子在玩家中仍然受欢迎，许多现代益智游戏都受到其机制的启发，包括 Stephen's Sausage Roll、Baba Is You 和 Patrick's Parabox。

Bobo 最近也在玩推箱子，发现完成一个关卡非常困难。感到沮丧的他抱怨道："成熟的箱子应该学会自己推动！"然后，叮！魔法发生了。突然，推动者从推箱子中消失了，你可以命令箱子自己推动。现在，游戏变得容易多了！……或者并非如此？

正式来说，你需要解决以下没有推动者的推箱子问题：

给定一个被墙壁包围的 $m \times m$ 二维网格，网格中可能还包含额外的内部墙壁。网格上有几个箱子和目标位置。箱子的数量等于目标位置的数量。保证没有箱子或目标位置占据墙壁单元，并且所有箱子和所有目标位置都位于不同的位置。

你可以重复执行以下操作：

• 选择任意一个箱子，并将其向四个基本方向（上、下、左或右）中的一个方向移动一格，前提是目标位置不是墙壁或另一个箱子。

你的任务是确定是否可以将所有箱子移动到目标位置。如果可以，构造一个这样的移动序列。

输入格式

输入的第一行包含三个整数 $n, m$ ($1 ≤ n, m \leq 50$)，分别表示地图的高度、宽度和箱子的数量。 接下来有 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示地图。每个字符属于集合 { #, ., @, *, !}，其中对于第 $i$ 行的第 $j$ 个字符 ($1 ≤ j \leq m$)：

• # 字符表示在位置 $(i, j)$ 有一堵墙；
• . 字符表示位置 $(i, j)$ 是空的；
• @ 字符表示在位置 $(i, j)$ 有一个箱子；
• * 字符表示在位置 $(i, j)$ 有一个目标位置；
• ! 字符表示在位置 $(i, j)$ 同时有一个箱子和一个目标位置。

地图被墙壁包围。输入保证箱子的数量等于目标位置的数量，并且地图中最多有 $50$ 个箱子。

输出格式

如果不存在有效的序列将所有箱子移动到目标位置，输出 -1。

否则，在一行中输出一个整数 $l$ ($0 ≤ l < 10^5$) ，表示移动序列的长度。然后，输出 $l$ 行，每行包含两个整数和一个字符：x y c ($1 ≤ x ≤ n, 1 ≤ y ≤ m, c ∈ \{L, R, U, D\}$) 。这表示当前位置为 $(x, y)$ 的箱子向左、右、下或上移动一步，即移动到 $(x, y - 1) 、(x, y + 1) 、(x + 1, y)$ 或 $(x - 1, y)$。请注意，你不应该将任何箱子移动到墙壁或另一个箱子上。

如果存在多个有效的移动序列，输出其中任何一个都将被视为正确。可以证明，在给定的约束下，如果存在任何有效的移动序列，则在 $10^5$ 步内存在这样的序列。

3 3
@.#
#.#
#.*

4
1 1 R
1 2 D
2 2 D
3 2 R

3 3
#@#
@!*
#*#

4
2 2 D
1 2 D
2 2 R
2 1 R

3 3
@#@
#..
**#

-1