Las torres perezosas
En un tablero de ajedrez las torres pueden moverse en horizontal y en vertical tantas casillas como quieran, pero siempre en línea recta. En nuestro caso, tenemos una torre perezosa que se mueve sólo hacia la derecha o hacia arriba y una casilla cada vez.
Si situamos a nuestra torre en la esquina inferior izquierda de un tablero de 3×3 y queremos que vaya a la esquina superior derecha, es fácil ver que tendrá que hacer como mínimo 4 movimientos, aunque puede seguir varias rutas distintas. En la siguiente figura aparecen dos de ellas:
Tiene sentido plantearse, ¿de cuántas formas distintas podría llegar nuestra torre desde el origen al destino con el mínimo número de movimientos posible? Una forma de hacer el cálculo es averiguar de forma iterativa el número de formas diferentes que tenemos de llegar hasta cada uno de los escaques intermedios. Empezamos anotando que sólo hay una forma para que la torre "vaya" de la casilla inicial a esa misma casilla inicial en el mínimo número de movimientos (no moviéndose):
Para las demás, sabemos que el número de maneras de llegar a un escaque en el mínimo número de pasos será la suma del número de formas de llegar a cada uno de los escaques adyacentes hacia la izquierda o hacia abajo (llegar a un escaque por arriba o por la derecha sería "ir hacia atrás"). Por tanto, lo que tenemos que hacer es ir calculando de cuántas formas se puede llegar a los escaques adyacentes de los ya conocidos sumando los números conseguidos anteriormente:
Repitiendo el proceso hasta llegar a la última celda tenemos:
Esto demuestra que en un tablero de 3×3 hay seis formas distintas de ir, con el mínimo número de movimientos posibles, de una esquina a otra.
Si en el tablero hay algunas casillas no transitables es necesario adaptar el recorrido para tenerlas en cuenta. Por ejemplo, en el siguiente tablero de 3×3 con una celda no transitable se puede llegar del origen al destino de tres formas distintas utilizando los cuatro movimientos mínimos:
Entrada
La entrada estará compuesta de varios tableros de distintos tamaños. Cada tablero comienza con una línea que contiene un número n (1 ≤ n ≤ 15) que indica el número de filas y columnas del tablero. A continuación aparecen n líneas, una por cada fila con n caracteres cada una. El carácter '.' (punto) indica una casilla transitable, mientras que 'X' significa casilla no transitable. Se garantiza que las casillas origen y destino siempre serán transitables.
La entrada termina con un tablero vacío que no debe procesarse.
Salida
Para cada caso de prueba se escribirá una línea con un único número que indica de cuántas formas distintas puede llegar nuestra torre perezosa desde la esquina inferior izquierda del tablero a la esquina superior derecha pasando por el mínimo número de casillas.
Se garantiza que el resultado nunca será mayor que 109.
Entrada de ejemplo
3 ... ... ... 3 ... X.. ... 0
Salida de ejemplo
6 3