BLINDESC  Blind Escape II
Illidan Stormage, the blind Warcraft hero is thrown in a maze for punishment. Being a blind hero, he cannot see anything but he can sense which direction is North, East, South and West.
Assume that the maze is laid out on a grid, and each grid location is either blocked or free or contains a demon. He has four possible moves: North, East, South, and West. Illidan starts from a free location at time t=0, and his goal is to kill all the demons within time T. Illidan kills a demon immediately (takes 0 unit of time) whenever he lands on a grid location containing a demon, however making a move to an adjacent cell takes exactly 1 unit of time. If Illidan attempts to move out of the grid or attempts to move to an obstacle, he will stay in his current location but it will still cost him 1 unit of time. When Illidan kills the last demon, he is immediately freed from the maze but if he fails to kill all the demons within time T, he will be trapped in the maze for eternity.
Keep in mind that Illidan is blind, so he may get confused while making a move. To avoid all this chaos, he decides to follow a rather simple strategy. Before he starts his journey to hunt and kill all the demons, he selects four real numbers: P_{N}, P_{E}, P_{S} and P_{W} denoting the probability to move North, East, South and West respectively. No matter where he is, he will always attempt to move North with probability P_{N}, East with probability P_{E}, South with probability P_{S}, and West with probability P_{W}.
Given the description of the maze, the location of all the demons, Illidanâ€™s starting position and the probabilities of each move, calculate the probability that Illidan will be able to kill all the demons before the time runs out.
Assume the grid will be of dimensions N x M and will contain K demons.
The second line contains three space separated integers, N, M and T, denoting the number of rows, the number of columns of the grid and the time by which Illidan needs to kill all the demons respectively. The third line contains four space separated real numbers P_{N}, P_{E}, P_{S} and P_{W} in that order. All these numbers will contain at most 2 digits after the decimal point.
Each of the next N lines will contain exactly M characters on each line describing the grid. The grid will only consist of the characters . @ # and *.
. indicates a free cell.
@ indicates Illidanâ€™s starting position which is also a free cell and will occur exactly once.
# denotes an obstacle.
* denotes the location of a demon, there can be at most one demon in a cell.
1 ≤ Q ≤ 5
1 ≤ N, M ≤ 8
1 ≤ T ≤ 16777216
1 ≤ K ≤ 3
P_{N} + P_{E} + P_{S} + P_{W} = 1
Or if you prefer a not so blind version SPOJ NBLINDESC Not So Blind Escape
Assume that the maze is laid out on a grid, and each grid location is either blocked or free or contains a demon. He has four possible moves: North, East, South, and West. Illidan starts from a free location at time t=0, and his goal is to kill all the demons within time T. Illidan kills a demon immediately (takes 0 unit of time) whenever he lands on a grid location containing a demon, however making a move to an adjacent cell takes exactly 1 unit of time. If Illidan attempts to move out of the grid or attempts to move to an obstacle, he will stay in his current location but it will still cost him 1 unit of time. When Illidan kills the last demon, he is immediately freed from the maze but if he fails to kill all the demons within time T, he will be trapped in the maze for eternity.
Keep in mind that Illidan is blind, so he may get confused while making a move. To avoid all this chaos, he decides to follow a rather simple strategy. Before he starts his journey to hunt and kill all the demons, he selects four real numbers: P_{N}, P_{E}, P_{S} and P_{W} denoting the probability to move North, East, South and West respectively. No matter where he is, he will always attempt to move North with probability P_{N}, East with probability P_{E}, South with probability P_{S}, and West with probability P_{W}.
Given the description of the maze, the location of all the demons, Illidanâ€™s starting position and the probabilities of each move, calculate the probability that Illidan will be able to kill all the demons before the time runs out.
Assume the grid will be of dimensions N x M and will contain K demons.
Input
The first line of the input contains an integer Q, denoting the number of test cases. Then the description of Q test cases follow. The first line of every test case will start with a blank line.The second line contains three space separated integers, N, M and T, denoting the number of rows, the number of columns of the grid and the time by which Illidan needs to kill all the demons respectively. The third line contains four space separated real numbers P_{N}, P_{E}, P_{S} and P_{W} in that order. All these numbers will contain at most 2 digits after the decimal point.
Each of the next N lines will contain exactly M characters on each line describing the grid. The grid will only consist of the characters . @ # and *.
. indicates a free cell.
@ indicates Illidanâ€™s starting position which is also a free cell and will occur exactly once.
# denotes an obstacle.
* denotes the location of a demon, there can be at most one demon in a cell.
Constraints
Output
For each test case, print the probability of Illidan escaping the maze in a single line. Error less than 10^{6} will be ignored.Sample Input
3 1 2 3 0 0.5 0 0.5 @* 1 8 64 0 0.5 0 0.5 @......* 8 8 10000000 0.05 0.25 0.45 0.25 ##....#. .##..... .*#.##.. .##..*#. ...###.. .#.#.... .#.#.#.. @#.*.#..
Sample Output
0.875000000000 0.693211582717 0.157323987423
Credits
Problem name and story inspired by LightOJ 1426  Blind EscapeOr if you prefer a not so blind version SPOJ NBLINDESC Not So Blind Escape
hide comments
:D:
20191125 20:54:39
Phenomenal problem. Pretty difficult. Had to redo my first solution attempt, but it was very fun finding and implementing the second one. The problems description is also high quality. Thanks for setting it up sgtlaugh. Now if I could just figure out how to get sub 1s :)


[Rampage] Blue.Mary:
20191115 02:17:31
Is there any special constraint on parameter K?

Added by:  sgtlaugh 
Date:  20191112 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem 