Problem E
Constrained Freedom of Choice

You live in a rectangular grid of ASCII characters. Your home is in the lower left corner and you work in the upper right corner. Sidewalks look like periods (.) and buildings, cars, trash cans and other obstacles look like pound signs (#). You walk to work each day by starting at your home and then moving one grid location at a time either up, down or to the right. You can’t move to the left (until it’s time to go home at the end of the day). Also, you refuse to step on the same location twice on your way to work. Thus in the figure shown, the two paths on the left would be legal ways to get to work, but the two on the right would not.

\includegraphics[width=1.0\textwidth ]{sample}

You like to take different paths to work each day. Given a map of your city, you would like to know how many different choices you have for getting to work. Two paths are different if they visit a different sequence of locations.


Input consists of multiple map descriptions. Each starts with a line containing a pair of positive integers, $r~ c$, giving the height and width of the map. This is followed by $r$ lines of characters, each $c$ characters long and each consisting of only periods and pound signs. The map is never larger than $10$ characters wide and $10$ characters tall and both the lower left and upper right locations are always periods. A value of zero for both $r$ and $c$ marks the end of input. The input contains at most $1\, 000$ map descriptions.


For each map, print out a line giving the number of different, legal paths that take you from your home to work. This number is less than $2^{31}$.

Sample Input 1 Sample Output 1
3 4
2 2
5 5
0 0

Please log in to submit a solution to this problem

Log in