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

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 $

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