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 crosssection, 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 topleft 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 previouslyuncollected 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 bottomleft and bottomright cells twice  however, it only collects the treasure in the latter cell the first time.
hide comments
buaavs_00:
20150220 16:04:24
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: 20150220 16:07:04 

:D:
20150210 22:26:46
I not sure if the field below fox start position is always nonempty (I got an assert fail on that). Add logic to your program to make the fox fall if there are empty fields below. 

Matija MartiniĆ¦:
20140529 16:19:33
my code is working fine in my machine.


785227:
20140526 20:25:29
Awesome problem. Enjoyed solving this :) 

Bharath Reddy:
20140406 10:15:18
AC in first attempt.


anurag garg:
20131225 06:49:51
take care of all the conditions..... Last edit: 20131225 06:50:19 

Martijn Muijsers:
20131025 14:17:12
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. :) 

I know nothing:
20130909 16:34:53
http://ideone.com/OF5RXe


Nitin Verma:
20130802 10:56:57
http://ideone.com/ZO3iEB


P_Quantum:
20130725 17:12:27
Finally accepted..!! 
Added by:  SourSpinach 
Date:  20130517 
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 