Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem E: 贪吃蛇

Problem E: 贪吃蛇

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 23  Solved: 8
[Submit][Status][Web Board]

Description

大家都熟悉一款贪吃蛇的游戏吧,假设蛇的活动区域在一个N*M的矩形网格,蛇是由L1*1的节点组成的。网格中'.'表示蛇可到达的区域,'#'表示不可达区域,'$'表示金币。

蛇可以选择将前进方向变为上下左右的任意一个,或在当前方向上前进一步,当蛇头的位置有金币时,蛇的金币数加1,金币消失,(此题假设蛇长不变)。当蛇头超出网格范围或撞上蛇的某一节点时或撞上障碍时,蛇会死亡,问蛇在M步操作后的状态。

Input

第一行一个整数T,表示数据组数,每组数据的第一行有两个正整数NM (1<=N<50, 1<=M<=50),分别表示网格的行数和列数,每组第2N+1行是一个N*M的字符矩阵,第N+2行有一个整数L(1<=L<=200)和字符串dirL表示蛇的长度,dir"LEFT" , "RIGHT", "UP", "DOWN"的一个,分别表示蛇初始时的前进方向为左,右,上,下。第N+3N+L+2行是对蛇位置的描述,每行两个整数X,Y(1<=X<=N,1<=Y<=M,XY列一定是'.'),依次表示从蛇头到蛇尾节点的行号和列号。第N+L+3行有一个整数P(1<=P<=200),表示有P次操作,接下来P行,每行一个字符串op,可能的值是"LEFT","RIGHT","UP","DOWN""GO",分别表示将当前方向变为左,右,上,下,和在当前方向上前进一步。蛇的位置在改变方向的操作中是不动的。输入保证初始时蛇一定是一条链(蛇的身体自身不会有交叉),蛇头的前进方向始终不会朝向蛇头的下一个节点,当某一步操作导致蛇死亡时后面将不会有其他操作。

Output

每组数据,如果蛇在M步操作后死亡,则输出两行,第一行一个"DEAD",第二行输出得到金币的个数。如果蛇没有死亡,则输出L+1行,前L行每行两个整数,依次表示在P次操作后,从蛇头到蛇尾节点的行号和列号,最后一行输出得到的金币数的个数。

Sample Input

1
6 10
....$..#.#
$...$.....
.#.$......
...#......
..#$....#.
.#.$...$..
4 UP
3 6
3 7
2 7
1 7
5
GO
GO
LEFT
GO
GO

Sample Output

1 4
1 5
1 6
2 6
1

HINT



S代表蛇头,*代表蛇身。





[Submit][Status][Web Board]