University of Toronto ACM-ICPC Tryouts 2012

C: 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 ≤ H ≤ 100) deep and W (1 ≤ W ≤ 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 ≤ N ≤ 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 ≤ T ≤ 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

Line 1: 1 integer, T
For each scenario:
Line 1: 3 integers, H, W, and N
Next H lines: W characters, representing the ith row of the grid, for i = 1..H
Next N lines: 1 character, representing the ith action, for i = 1..N

Output

For each scenario:
Line 1: 1 integer, the number of treasures collected in total.

Sample Input

2
2 3 4
DDD
TES
R
D
R
L
3 2 6
TE
TE
ET
R
R
L
R
L
R

Sample 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.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)