Los caminos por la obra

Enunciado

Natalia reparte paquetes en bicicleta por un barrio de calles rectas. Sale de la esquina de arriba a la izquierda y entrega en la de abajo a la derecha, y todas las calles son de un sentido: de cada esquina solo puede seguir a la esquina de la derecha o a la de abajo. Este mes hay obras y algunas esquinas están cerradas, así que por esas no pasa. Le dio curiosidad saber de cuántas maneras distintas puede hacer el reparto.

Escribe una función que reciba ciudad, una lista de textos, uno por renglón de esquinas y todos del mismo largo. Cada carácter es una esquina: . si está libre y # si está cerrada. Hay de 1 a 17 renglones y de 1 a 17 esquinas en cada renglón.

Regresa un entero: cuántos caminos distintos llevan de la esquina de arriba a la izquierda a la de abajo a la derecha pasando solo por esquinas libres. Si la esquina de donde sale o la esquina donde entrega está cerrada, no hay ninguno: regresa 0.

Con ["...", ".#.", "..."] regresa 2: con la obra en el centro solo quedan el camino que va todo a la derecha y luego todo abajo, y el que va todo abajo y luego todo a la derecha. Si el barrio es de una sola esquina y está libre, Natalia ya está donde entrega, y eso cuenta como un camino: regresa 1.

Cuidado con el tamaño: en un barrio de 17 por 17 puede haber cientos de millones de caminos, así que recorrerlos uno por uno no cabe en el tiempo del motor. Muchos caminos comparten el mismo tramo, así que no conviene recalcular lo mismo dos veces.

Ejemplos

• El ejemplo

  ["...", ".#.", "..."] → 2

• Sin obras, dos renglones

  ["...", "..."] → 3

• Una sola esquina

  ["."] → 1

• La esquina donde entrega está cerrada

  ["..", ".#"] → 0

Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.

Empiezas con esto

def rutas(ciudad):
    pass

function rutas(ciudad) {
}