I'm getting WA in this problem, but my program seems to be correct.
I noticed, however, that if the probabilities of reaching monsters and coins are very low, my program underflows and outputs wrong answer. For example, the following maze has a "snake" path with a coin, a monster and a wall in some point. If the position of thecoin/monster/wall is as shown, the answer should be 12.0, but my program outputs something a little lower. If the triple moves farther in the snake, the answer drops and reaches 0.0.
15 15
$A.............
aaaaaaaaaaaaaa.
.........#!1...
.aaaaaaaaaaaaaa
...............
aaaaaaaaaaaaaa.
...............
.aaaaaaaaaaaaaa
...............
aaaaaaaaaaaaaa.
...............
.aaaaaaaaaaaaaa
...............
aaaaaaaaaaaaaa.
...............
I would like to know if my program gets WA for numerical reasons like this, so I can tackle this problem, or if I did something really wrong. The test case above is very artificial, I don't know if there is anything like that in the input files.
Can anybody help, please? Maybe some tricky test cases will do.
Another maze:
15 15
.......#.......
........#.3....
...$.....#..#..
..........#..#.
..........#.#..
...........a...
####.#.
Z!.......#...#.
!.........###..
...............
..............b
...3....###.
.z#........#...
..###.....#....
...B#....#...A
My answer: 3.243033
Thanks!
Carlos