Escape X07059


Statement
 

pdf   zip

html

Neo is trying to escape from Agent Smith and his copies. He is currently at the top left corner of the Matrix and has to reach the bottom right corner as fast as possible. Neo can only run down or to the right, else Agent Smith will have time to catch him. In addition, some of the cells of the Matrix are blocked.

To confuse Agent Smith, Neo has gained the ability to create virtual copies of himself. Neo can create one virtual copy of himself for each distinct path through the Matrix. Help Neo compute how many virtual copies he needs to create.

Input

The input consists of several test cases. Each test case starts with the number of rows 1≤ n≤ 20 and the number of columns 1≤ m≤ 20 of the Matrix. This is followed by n rows with m characters each. The character "." indicates a free cell of the Matrix, while "#" indicates a blocked cell. The top left and bottom right corners are always free.

Output

For each test case, a number on a single line indicating the number of virtual copies Neo needs to create.

Public test cases

  • Input

    3 3
...
...
...

    Output

    6

  • Input

    4 4
..#.
#..#
.#..
..#.

    Output

    1

  • Input

    2 3
..#
.#.

    Output

    0
    • Information
    Author
    Anders Jonsson
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++