Filling the maze
All submissions for this problem are available.
Consider a maze like this one, encoded in ASCII as a grid of R by C cells, denoted by characters # (a wall) and o (a walkable cell). The top left cell of the maze is the start and the bottom right one is the goal. All walkable cells are initially white.
Cell B is reachable from cell A iff A and B are both walkable and it's possible to get to B by starting at A and moving only to walkable cells in the four cardinal directions — up, right, down and left.
The maze is complicated and you're too lazy. That's why you try to solve it using the following algorithm:
- Pick a white walkable cell at random and click on it.
- The cell you picked in the first step and all cells reachable from it turn red.
- If there's a red path from the start to the goal, you have solved the maze.
- Else: goto first step.
(Note that once a cell turns red, it will remain red until the maze is solved. Also note that this algorithm will always terminate.)
What's the expected number of clicks (expectation value of the number of clicks) you'll have to make to solve the maze?
The first line of input contains an integer T denoting the number of test cases.
- The first line of each test case contains two positive integers R and C — the number of rows and columns of the maze, respectively.
- The following R lines each contain C characters. Each character is either # or o.
For each test case, output a single line containing one real number: the expected number of clicks necessary to solve the maze.
- 1 ≤ T ≤ 100
- subtask 1 (15 pts): 1 ≤ RC ≤ 30
- subtask 2 (85 pts): 1 ≤ RC ≤ 50000
- At least one path from the start to the goal exists in each test case.
Input: 2 3 3 o#o oo# #oo 2 2 oo oo Output: 1.166666667 1.000000000
Example case 1. With 5/6 chance, the first click you'll make will be on the only path from the start to the goal. With 1/6 chance, you'll click on the top right cell before that. The expected number of clicks is therefore 5/6*1+1/6*2.
|Tags||bfs, dfs, expected-value, medium-hard, probability, sept15, xellos0|
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.