Time Limit: 1 second
Memory Limit: 32 Mb
You are lost in a vast forest with nothing but monkeys and budgies for company. For days you have been trying to find your way out, but no matter how hard you try, you seem to find yourself back where you started. Resigned, you decide to stay put and wait for a rescue party.
Days and nights pass, until finally a search robot stumbles upon you and brings you food, water and a powerpoint to recharge your laptop! It's not the rescue party you were hoping for, but you're saved. Well, nearly.
The robot is unable to tell you how to get back to the rescue party. All it can do is print out a map of the forest, the location at which it found you, and the steps that it took from the rescue party in order to find you. Unfortunately there is a bug in the robot's program — if the robot tried to move into a tree or step outside the forest, it would still record this step, but it would not actually move.
For example, imagine the forest as the grid below, with some of the squares containing trees. If the robot started at grid square (5,2) and took the steps E, E, E, S, S, W, it would finish in square (7,3) where you are waiting (note that it does not actually move during the second S step because there is a tree in the way).
On the other hand, suppose the robot started at square (7,1) and again took the steps E, E, E, S, S, W. Once more it would finish in (7,3) where you are (this time it does not move during the second or third E because this would take it outside the forest). In fact the robot might have started in any of the locations (7,1), (8,1), (5,2), (6,2), (7,2), (8,2), (7,3) or (8,3), and it still would have finished where you are standing.
Note that the robot is allowed to start in the square where you are waiting, and/or may travel through your square any number of times along the way (you were probably elsewhere chatting with a monkey at the time). However, the robot may not start in a square containing a tree, and it may not start outside the forest.
Given the map of the forest, your current location, and the steps taken by the robot to get to you, your task is to find the number of possible locations at which the robot may have started its trek to find you.
Your program must read from standard input. The first line will contain the integers w h separated by a single space, as described above. Following this will be h lines, each describing a row of the forest map. Each of these lines will contain w characters. These characters will be one of:
.' — an empty patch of ground;
T' — a tree;
U' — the location at which the robot finds you.
U' will appear exactly once on the map.
This will be followed by a line containing the integer p, then p
lines describing the steps the robot took to find you. Each of these
lines will contain a single letter —
W — corresponding to steps in the north, east, south or
west directions, respectively.
You are guaranteed that there is at least one possible starting point
that will get the robot to you using this sequence of steps.
All letters in the input will be given in upper case.
Your program must write a single line to standard output. This line must contain a single integer giving the number of possible locations at which the robot might have started.
8 6 .T...T.. T....... ..T..TU. ....T..T ...T.... ..T.T.T. 6 E E E S S W
The score for each input scenario will be 100% if the correct answer is output, or 0% otherwise.