Scape from the maze P88921
Write a program to compute the number of different paths that allow us to scape from a given maze, by going from the bottom-right cell to the upper-left cell. Every movement must be upwards or to the left. There are prohibited cells that we cannot pass by. There is always at least one path from the entrance to the exit.
Input
Input consists of several cases. Every case begins with the number of rows n and the number of columns m, followed by n lines with m characters each. An ‘X’ indicates a forbidden cell, and a dot indicates a free cell. A special test with n = m = 0 marks the end of input. You can assume 2 ≤ n ≤ 40 and 2 ≤ m ≤ 40.
Output
For every case, print the number of different paths that go from the bottom-right corner to the upper-left corner, with all the movements upwards or to the left. If this number is greater than or equal to 106, instead print “!!!”.
Hint
The fact that some cell has too many paths from the entrance (or to the exit) does not imply for sure that there are too many paths from the entrance to the exit.
Input
2 2 .. .. 3 8 .......X .X.X.X.. X....... 7 38 ...................................... ...................................... ...................................... ...................................... ...................................... ...................................... ...................................... 2 40 ........................................ ......................................X. 2 40 .X...................................... ........................................ 0 0
Output
2 4 !!! 1 1
- Author
- Omer Giménez
- Language
- English
- Translator
- Carlos Molina
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++ Python Python
- User solutions
- C++ Python