P11864 「o.OI R1」α+β Problem

机器人小 $\alpha$ 喜欢做游戏，机器人小 $\beta$ 喜欢玩游戏。

现在，它们正在玩一个叫作推箱子的游戏！ 机器人小 $\beta$ 为关卡制定了一个用字符串表示的移动路径： |字符|含义| | :-----------: | :-----------: | |`W`|让机器人前进一格| |`S`|让机器人后退一格| |`A`|让机器人左转| |`D`|让机器人右转| 身为机器人小 $\alpha$，你需要构造一个 $n\times m$ 的地图： |字符|含义| | :-----------: | :-----------: | |`\|`|机器人无法穿过的墙壁|| |`X`|机器人最开始在的位置| |`S`|箱子最开始所在的位置| |`.`|空地| 注意每个位置的东西只能是以上四种之一。 机器人的初始位置是给定的，方向朝上，地图外都是墙。 小 $\beta$ 完成移动后，所有箱子都必须移动过，小 $\alpha$ 需要让这个地图的箱子数最多，且小 $\beta$ 每步操作都合法。 以下给出所有不合法的操作： |操作|不合法情况| | :-----------: | :-----------: | |`W`|机器人前方是墙| |`W`|机器人前方两格都是箱子| |`W`|机器人前方两格分别是箱子和墙| |`S`|机器人后方是箱子或墙| 小 $\alpha$ 需要一份程序来完成这份工作。

无

无

部分样例有其他正确答案。 **「数据范围」** **本题开启 Special Judge 与捆绑测试。** 一个测试点内，如果对于每组数据你的箱子数是最多的，且方案合法，你才能获得该测试点的分数。 只有通过一个子任务内的所有测试点才能得到该子任务的分数。 对于所有测试数据，保证： - $1\leq n,m\leq 2000$，$1\leq \sum nm\leq 4\times 10^6$。 - $1\leq x\leq n$，$1\leq y\leq m$。 - $1\leq k,\sum k\leq 10^6$。 - $s_i\in\{\texttt{W},\texttt{A},\texttt{S},\texttt{D}\}$。 - 小 $\beta$ 的移动在空旷地图下一定合法。 | 子任务 | $n,m$ | $\sum nm$ | $\sum k$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:|:-:| |$0$ | $\leq4$ | $\leq 40$ | $\leq100$ | 无 | $10$ | |$1$ | $=45$ | $=2025$ | $\leq10^3$ | A | $10$ | |$2$ | $\leq200$ | $\leq 4\times 10^4$ | $\leq10^3$ | 无 | $20$ | |$3$ | $\leq1000$ | $\leq 2\times 10^6$ | $\leq10^6$ | B | $15$ | |$4$ | $\leq1000$ | $\leq 2\times 10^6$ | $\leq10^6$ | C | $20$ | |$5$ | $\leq2000$ | $\leq 4\times 10^6$ | $\leq10^6$ | 无 | $25$ | - 特殊性质 A：前进和后退的总次数不超过 $20$ 次，且 $x=y=23$。 - 特殊性质 B：$s_i\in\{\texttt{W},\texttt{A},\texttt{D}\}$，且只会朝两个方向前进。 - 特殊性质 C：可放箱子的最大数量为 $0$ 或 $1$。 --- 尽管比赛中不会返回，我们仍将告诉你 Special Judge 会返回的对应信息，优先级递减。 - `Error: 1`：出现规定以外的字符。 - `Error: 2`：出生点不在正确的位置。 - `Error: 3`：机器人无法前进。 - `Error: 4`：机器人无法后退。 - `Error: 5`：有箱子没有被推动过。 - `Error: 6`：箱子数不是最多的。 - `Correct`：测试点通过。