UOFTAC - Foxhole

Everyone knows that Foxen love digging holes. You've been observing one Fox in particular, who's preparing to burrow underground in search of treasures. When viewed from the side, as a cross-section, his digging site can be represented as a grid of cells, $H$ ($1 \leq H \leq 100$) deep and $W$ ($1 \leq W \leq 100$) across. Every cell contains either dirt (represented by "D"), stone ("S"), empty space ("E"), or a treasure ("T"). The surface can also be traversed, effectively giving the grid an additional row of empty cells above the topmost row.

The Fox starts immediately above the top-left cell, which is guaranteed to not be empty. It has a set of $N$ ($1 \leq N \leq 1000$) actions in mind before it starts its dig, which it will execute in order. Each action consists of moving either left (represented by "L"), right ("R"), or down ("D") by one cell. If the cell that the Fox would move to contains stone, or is beyond the boundaries of the grid in any direction, it will skip that action. If it enters a cell with a previously-uncollected treasure, it will collect it, leaving the cell empty. If the cell immediately below the Fox is ever empty, it will fall down until this is no longer the case. Note that collecting treasure occurs before falling, and that the Fox stops falling if it hits the bottom of the grid.

There are $T$ ($1 \leq T \leq 20$) scenarios as described above. For each one, you'd like to determine how many treasures the Fox will collect throughout the course of its dig.

Input

First line: 1 integer, $T$

For each scenario:

First line: 3 integers, $H$, $W$, and $N$

Next $H$ lines: $W$ characters, representing the $i$th row of the grid, for $i = 1..H$

Next $N$ lines: 1 character, representing the $i$th action, for $i = 1..N$

Output

For each scenario:

1 integer, the number of treasures collected in total.

Example

Input:
2
2 3 4
DDD
TES
R
D
R
L
3 2 6
TE
TE
ET
R
R
L
R
L
R
Output: 1
2

Explanation of Sample:

In the first scenario, the Fox moves right along the surface, then digs down to the first row. As the cell below it is empty, it immediately falls to the 2nd row. It ignores its next action, as the cell to its right is filled with stone, and finally moves left to claim a treasure.

In the second scenario, it moves to the right and promptly falls all the way down to the 2nd row. Because the Fox is already in the rightmost column, it ignores the action to move right. It then moves left, collects the treasure there, and then falls to the bottom row. Finally, it moves back and forth between the bottom-left and bottom-right cells twice - however, it only collects the treasure in the latter cell the first time.


Added by:SourSpinach
Date:2013-05-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem, used in the 2012 UofT ACM Tryouts

hide comments
2019-12-17 22:47:32 Simes
I too asserted that the cell beneath the foxen start position is not empty, and it passed ok.
2015-02-20 16:04:24 buaavs_00
Finally AC. C users pay attention to your input. You can't just sacanf("%s") without sacanf("%c") because there is the nl char at the end of line

Last edit: 2015-02-20 16:07:04
2015-02-10 22:26:46 :D
I not sure if the field below fox start position is always non-empty (I got an assert fail on that). Add logic to your program to make the fox fall if there are empty fields below.
2014-05-29 16:19:33 Matija MartiniƦ
my code is working fine in my machine.
but spoj giving runtime error for that..
i am taking input of description of digging site using scanf("%s",a[i]).??
is this correct..??

after replacing scanf to cin... AC.. :)

Last edit: 2014-05-29 16:51:23
2014-05-26 20:25:29 785227
Awesome problem. Enjoyed solving this :)
2014-04-06 10:15:18 Bharath Reddy
AC in first attempt.
If you pass the test cases given in this page, then your program mostly works. No need of other special cases.
2013-12-25 06:49:51 anurag garg
take care of all the conditions.....

Last edit: 2013-12-25 06:50:19
2013-10-25 14:17:12 Martijn Muijsers
Kind of unmentioned: the fox stops falling on dirt, stone but also on top of a treasure. The fox will walk over treasure. The fox can go down into a treasure cell if it wants to collect it. :)
2013-09-09 16:34:53 I know nothing
<snip>
plz tell why my code is giving WA

Last edit: 2023-05-19 21:50:37
2013-08-02 10:56:57 Nitin Verma
<snip>
please, tell me why i am getting wrong answer.


Last edit: 2023-05-19 21:50:41
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.