PION贪吃蛇
题目背景
NOIP2018原创模拟题 T3
NOIP DAY1 T3 or DAY 2 T2 难度
贪吃蛇大家都玩过吧,当然不同版本有不同规则。下面介绍PION贪吃蛇。
题目描述
![图A](https://cdn.luogu.com.cn/upload/pic/31298.png)
***表示方法:***
该题中贪吃蛇存在于一个n行m列的矩形中,用 ‘.’ 表示空地,用 '#’ 表示蛇身,用 ‘@’表示蛇头,用‘&’表示食物
例如:图一表示 $5*6$ 的矩形,有一条蛇,蛇长度为 $7$,有两个食物
***基本规则:***
1.蛇头每一秒就会移动一格,身体自然会跟着移动,用W表示向上,S表示向下,A表示向左,D表示向右
2.蛇每吃一个食物就长度就会加一,而增加的长度体现在食物所在的地方,你可以把吃食物理解成食物变成了蛇头,之前的蛇头变成了蛇身,这一秒不移动
例如:图二的三幅图展示了第一秒,第二秒,和第三秒的情况
3.蛇如果死亡,身体(包括头)一定会全部变成食物
4.PION贪吃蛇的蛇头碰到自己或别的蛇的身体就会死亡
例如:图三的三幅图展示了第二条蛇撞在别人身体上死亡的过程
5.蛇头撞在边界上也会引起死亡,但蛇头刚好现在边界上不会
例如:图四第二幅图虽然蛇头在边界上,但是只是刚好,如果此时进行D操作蛇就会死亡,如果进行W或S就不会
6.如果有操作使蛇头向相反方向运动,之后如果与身体重合蛇也会死亡(比如:图二第一幅图使用A操作,蛇就会死亡,此时在原地成为三个食物,你也可以理解为蛇下一秒不行动而自杀了)
7.两条蛇蛇头相撞,主动撞上的死亡
8.蛇的移动按编号由小到大进行(编号的含义见下文)
输入输出格式
输入格式
第一行三个数 $n,m,k$ 表示 $n*m$ 的矩形,$k$ 表示操作次数
接下来 $n$ 行每行 $m$ 个字符,表示地图
再接下来 $c$ 行(注意:图中有几条蛇就有几行),每行 $k$ 个字符,表示有 $k$ 个操作(如果执行了某个操作蛇死了,就忽略后面的操作)
我们将蛇编号:按每条蛇蛇头的坐标从小到大编号为 $1,2,...,c$(越靠近上边的坐标越小,如果相同越靠近左边的坐标越小)
例如:图三第一幅图两条蛇的蛇头坐标分别为($4,3),(3,7)$所以较长的蛇编号为 $2$,较短的蛇编号为 $1$
输出格式
$c+1$ 行,输出 $k$ 次操作后每一条蛇的长度,编号;每一行第一个为长度,第二个数为编号
最后一行输出剩下食物的总个数
注意:输出按长度由大到小排序(长度相同按编号由小到大排序),死亡的蛇长度为 $0$
输入输出样例
输入样例 #1
5 7 6
.&...&.
..##@..
.&...&.
..##@..
.&...&.
DWAAAA
WDDDDD
输出样例 #1
5 1
0 2
7
输入样例 #2
9 9 4
.........
.#######.
.......#.
.@#.&@.#.
&.#.&&.#.
&&######.
.&.......
..@####..
.........
ASSD
ASDD
WASD
输出样例 #2
22 1
4 2
0 3
6
说明
***样例说明:***
![图B](https://cdn.luogu.com.cn/upload/pic/31357.png)
图五,图六展示了从第 $0$ 秒开始之后每一秒地图的状态,请看图理解(样例二图四有点小错误)
***数据范围:***
$10\%$ 数据满足 $n,m\leq 5,c=1,k\leq3$
$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$,且图中的蛇不会引起混淆(对于任意蛇头,最多只有一块蛇身于其相连,而蛇身最多为二连块),且数据保证图中的蛇均可以判断身体与头的对应关系,不会造成蛇身形态多解