Calculate probabilty to escape the maze

Question

I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement

The Frog is in an two-dimensional maze represented as a table. The maze has the following characteristics:

1. Each cell can be free or can contain an obstacle, an exit, or a mine.
2. Any two cells in the table considered adjacent if they share a side.

3. The maze is surrounded by a solid wall made of obstacles.

4. Some pairs of free cells are connected by a bidirectional tunnel.

When the frog is in any cell, he can randomly and with equal probability choose to move into one of the adjacent cells that don't contain an obstacle in it. If this cell contains a mine, the mine explodes and the frog dies. If this cell contains an exit, then the frog escapes the maze.

When the frog lands on a cell with an entrance to a tunnel, he is immediately transported through the tunnel and is thrown into the cell at the other end of the tunnel. Thereafter, he won't fall again, and will now randomly move to one of the adjacent cells again. (He could possibly fall in the same tunnel later.)

It's possible for the frog to get stuck in the maze in the case when the cell in which he was thrown into from a tunnel is surrounded by obstacles on all sides.

So I get input as

The first line contains three space-separated integers n, m and k denoting the dimensions of the maze and the number of bidirectional tunnels.

The next n lines describe the maze. The i'th line contains a string of length m denoting the i'th row of the maze. The meaning of each character is as follows:

1. # denotes an obstacle.
2. A denotes a free cell where the frog is initially in.
3. * denotes a cell with a mine.
4. % denotes a cell with an exit.
5. O denotes a free cell (which may contain an entrance to a tunnel).

The next k lines describe the tunnels. The i'th line contains four space-separated integers i1,j1, i2, j2. Here (i1,j1) and (i2, j2) denote the coordinates of both entrances of the tunnel. (i,j) denotes the row and column number, respectively.

So for 1st use case input is

3 6 1
###*OO
O#OA%O
###*OO
2 3 2 1

Answer for this is 0.25. Total possible path could be frog gets stuck (1,1) cell + can die two times (2 mines) + Exit. So probability is 1/4

But for below use case am not able to deduce the correct probability.

7 7 2
O**%**O
OOOOOOO
OOO*OOO
**OA###
OOOO#OO
O*OO#O%
OOOO#OO
1 1 7 7
6 4 6 6

Answer should be 0.13344359 my answer is 0.2

I wrote a DFS to calculate all the end state a frog could be. In this case 2 exit + 8 mines + 0 stuck.

prob = Double.valueOf(maze.exit.size())/Double.valueOf(maze.exit.size()+maze.mines.size()+maze.stuck.size());

private static void dfs(Vertices v, Maze m, Vertices[][] edgeTo) {
        m.setMark(v.x, v.y, true);

        if(!m.neighbours(v).isEmpty()) {
            for (Vertices w : m.neighbours(v)) {
                if (w!=null) {
                    edgeTo[w.x][w.y] = v;
                    if(!m.marked(w.x, w.y)) {
                        dfs(w, m, edgeTo);
                    }
                    if(w.state.equals("%")) {
                        m.addExit(w); 
                    } else if(w.state.equals("*")) {
                        m.addMines(w);
                    }
                }
            }
        } else if(!v.state.equals("*") && !v.state.equals("%")) {
            m.addStuck(v);
        }
    }

can someone help to explain the correct probability in this use case?

Answer 1

First of all, note that you should use pseudo-code in your question to make it readable by anyone.

You cannot treat this problem by just listing possible ends and give them equal probability. Consider this trivial case with no tunnel:

%AO*

the frog does not have a total 50 % to escape. On first move it has 50 % to go left to exit and 50 % to go right. But if it goes right it has 50 % to die on the mine and 50 % to come back on initial cell. Finally you build the series:

• to exit $\sum_n \frac{1}{2^{2n+1}} = 2/3$
• to die $\sum_n \frac{1}{2^{2n+2}} = 1/3$

Of course finding the series expression can be very complicated on hard mazes. So how to solve this problem ? You can for example use a dynamic programming solution.

The sub-problem is having the probabilities for the frog to be on any cell after the $k^{th}$ move, what are the probabilities after the $(k+1)^{th}$ move ? These probabilities also contain exit and death.

So let's take again the small example %AO*, indexing the cells 1 to 4 from left to right.

• at $k=0$, the frog is on cell 2 so $P(2) = 100 \%$,
• at $k=1$, the frog moves left or right, so $P(exit) = 50\%$, $P(3)=50\%$,
• at $k=2$, $P(exit) = 50 \%$, $P(2) = 25 \%$, $P(dead)=25\%$

ans so on, until $P(exit) + P(dead)$ is sufficiently close to 100 % for the precision you need.

Due to tunnels or even from start position, there may be some cells unable to reach a mine, an exit or any of them (as your first example). You should first investigate this, any cell that cannot reach an exit shoud be considered as a mine. And a cell that cannot reach a mine but can reach an exit should be considered as an exit. This will prevent any infinite loop and save some time.