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:
- Each cell can be free or can contain an obstacle, an exit, or a mine.
- Any two cells in the table considered adjacent if they share a side.
The maze is surrounded by a solid wall made of obstacles.
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:
- # denotes an obstacle.
- A denotes a free cell where the frog is initially in.
- * denotes a cell with a mine.
- % denotes a cell with an exit.
- 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?