Grid Paths.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

Considere una cuadrícula $n$ ~n~ x $n$ ~n~ cuyas casillas pueden tener trampas. No está permitido moverse a una casilla con trampa. Su tarea consiste en calcular el número de caminos desde la casilla superior izquierda hasta la casilla inferior derecha. Sólo puedes moverte hacia la derecha o hacia abajo.

Entrada

La primera línea de entrada tiene un número entero $n$ ~n~: el tamaño de la cuadrícula. Después de esto, hay $n$ ~n~ líneas que describen la cuadrícula. Cada línea tiene $n$ ~n~ caracteres: $.$ ~.~ denota una casilla vacía, y $*$ ~*~ denota una trampa.