背景

NOIP2018原创模拟题 T3

NOIP DAY1 T3 or DAY 2 T2 难度

贪吃蛇大家都玩过吧，当然不同版本有不同规则。下面介绍PION贪吃蛇。

题目描述

表示方法：

该题中贪吃蛇存在于一个 $n$ 行 $m$ 列的矩形中，用 . 表示空地，用 # 表示蛇身，用 @ 表示蛇头，用 & 表示食物。
例如：图一表示 $5 \times 6$ 的矩形，有一条蛇，蛇长度为 $7$，有两个食物。

基本规则：

1. 蛇头每一秒就会移动一格，身体自然会跟着移动，用 W 表示向上，S 表示向下，A 表示向左，D 表示向右。

2. 蛇每吃一个食物就长度就会加一，而增加的长度体现在食物所在的地方，你可以把吃食物理解成食物变成了蛇头，之前的蛇头变成了蛇身，这一秒不移动。

例如：图二的三幅图展示了第一秒，第二秒，和第三秒的情况。

3. 蛇如果死亡，身体（包括头）一定会全部变成食物。

4. PION贪吃蛇的蛇头碰到自己或别的蛇的身体就会死亡。

例如：图三的三幅图展示了第二条蛇撞在别人身体上死亡的过程。

5. 蛇头撞在边界上也会引起死亡，但蛇头刚好现在边界上不会。

例如：图四第二幅图虽然蛇头在边界上，但是只是刚好，如果此时进行 D 操作蛇就会死亡，如果进行 W 或 S 就不会。

6. 如果有操作使蛇头向相反方向运动，之后如果与身体重合蛇也会死亡（比如：图二第一幅图使用 A 操作，蛇就会死亡，此时在原地成为三个食物，你也可以理解为蛇下一秒不行动而自 sha 了）。

7. 两条蛇蛇头相撞，主动撞上的死亡。

8. 蛇的移动按编号由小到大进行（编号的含义见下文）。

输入格式

第一行三个数 $n,m,k$ 表示 $n \times m$ 的矩形，$k$ 表示操作次数。

接下来 $n$ 行每行 $m$ 个字符，表示地图。

再接下来 $c$ 行（注意：图中有几条蛇就有几行），每行 $k$ 个字符，表示有 $k$ 个操作（如果执行了某个操作蛇死了，就忽略后面的操作）。

我们将蛇编号：按每条蛇蛇头的坐标从小到大编号为 $1,2,\ldots,c$（越靠近上边的坐标越小，如果相同越靠近左边的坐标越小）。

例如：图三第一幅图两条蛇的蛇头坐标分别为 $(4,3),(3,7)$，所以较长的蛇编号为 $2$，较短的蛇编号为 $1$。

输出格式

$c+1$ 行，输出 $k$ 次操作后每一条蛇的长度、编号；每一行第一个为长度，第二个数为编号。

最后一行输出剩下食物的总个数。

注意：输出按长度由大到小排序（长度相同按编号由小到大排序），死亡的蛇长度为 $0$。

5 7 6
.&...&.
..##@..
.&...&.
..##@..
.&...&.
DWAAAA
WDDDDD

5 1
0 2
7

9 9 4
.........
.#######.
.......#.
.@#.&@.#.
&.#.&&.#.
&&######.
.&.......
..@####..
.........
ASSD
ASDD
WASD

22 1
4 2
0 3
6

提示

样例说明：

图五、图六展示了从第 $0$ 秒开始之后每一秒地图的状态，请看图理解（样例二图四有点小错误）。

数据范围：

$10\%$ 的数据满足 $n,m \leq 5,\ c=1,\ k \leq 3$。

$30\%$ 的数据满足 $n,m \leq 10,\ c \leq 2,\ k \leq 5$。

$50\%$ 的数据满足 $n,m \leq 50,\ c \leq 5,\ k \leq 20$。

$70\%$ 的数据满足 $n,m \leq 100,\ c \leq 7,\ k \leq 50$。

$100\%$ 的数据满足 $n,m \leq 200,\ c \leq 20,\ k \leq 100$，且图中的蛇不会引起混淆（对于任意蛇头，最多只有一块蛇身与其相连，而蛇身最多为二连块），且数据保证图中的蛇均可以判断身体与头的对应关系，不会造成蛇身形态多解。