Scape from the maze P88921


Statement
 

pdf   zip

html

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.

Public test cases
  • 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
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++