Dexter is drunk
All submissions for this problem are available.
Dexter has had too much Robooz(alchoholic drink for robots). Normally he can move in four directions Up, Down, Left and Right. His CPU sends the "move up" signal to his movement board and then he physically moves up. Now his CNS(Central Neuelectrical System) is malfunctioning which connects his to CPU to his movement board. Because of this if his CPU sends the "move up" signal, there is a probability(in percentage) P(up, up) that he will physically move up and there is equal chance that he will move down, left or right. To be exact,
P(up, down) = P(up, left) = P(up, right) = (100-P(up, up)) / 3 in this case.
The other signals "move down", "move left" and "move right" now work in the same way. Once a signal is mapped to a direction, it will always correspond to that direction. For example, if "move up" is mapped to down (this event has probability P(up, down). "move up" will move the robot down always after this.
Dexter is still in the club and wants to leave the club. The club is represented by a N x M grid. His position is denoted by 'S' and the exit is denoted by 'E'. Cells represented by '.' are paths where he can walk on. '#' represents obstacles(other robots, walls etc.). You have to find the total probability that he will reach the exit successfully (not necessarily in the shortest path).
First line contains T the number of test cases.
For each test case,
- First line contains four integers P1, P2, P3 and P4, the probability of up mapping to up, down to down, left to left and right to right respectively.
- Next line contains two integers N and M, number of rows and columns.
- N lines follow, each containing M characters.
For each test case print a line containing the probability in percentage(Relative error upto 10^-2 allowed).
1 <= T <= 1000
0 <= P1, P2, P3, P4 <= 100
1 <= N, M <= 100 and N*M > 1
The grid will contain only 'S', 'E', '.' and '#'
'S' and 'E' will occur exactly once.
100 100 0 50
100 100 100 100
Case #1: Dexter has to go left to reach the exit. The only way is by "move right" signal which has 16.666667% chance to go left.
Case #2: Dexter can move in all directions always. Hence the probability is 100%
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.