Problem D: Dash to Vince Problem D: Dash to Vince
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 401 Solved: 166
[Submit][Status][Web Board]Description
Yee_172 is in a maze of n row and m columns. He is in position S and he wants to go to position V since he wants to find his friend Vince. Vince has told Yee_172 how to find position E by giving Yee_172 a sequence of directions: 01123321……. It confuses Yee_172 because Vince only told him that 0123 means four directions, but not specifically up, left, right, or down. (i.e. the mappings relationship between the digits and specific directions are unknown)
Therefore, Yee_172 turns for your help. You need to calculate the number of mappings of digits to directions that will lead Yee_172 to Vince.
Input
The first line is T, which is the number of test cases, (T <= 10);
For each test case, the first line will be integer n, m, and then n lines following, each line contains m characters (‘#’ means a beautiful girl, if Yee_172 go to ‘#’, he will stop finding Vince, ‘S’ is the start point and ‘E’ is Vince point.) N, m <= 50;
After the n lines, there will be one line contains 0, 1, 2, 3 only, meaning the sequence Yee have, which has a length of no more than 100.
Output
For each test case, print a single integer, which the number of directions permutation that leads the Yee_172 to the Vince.
Sample Input
2
5 6
.....#
S....#
.#....
.#....
...E..
333300012
5 3
...
.S.
###
.E.
...
3
Sample Output
1
0
HINT
[Submit][Status]