Fondo

He construido una carrera de obstáculos simple colocando cajas en una habitación rectangular. Ahora quiero contar la cantidad de formas esencialmente diferentes en las que se puede resolver. Necesito que me escribas un programa para eso.

Entrada

Su entrada es una matriz rectangular no vacía de los caracteres .#. Los puntos .son espacios vacíos, y #son obstáculos.

Un camino a través de la carrera de obstáculos comienza en la esquina superior izquierda y termina en la esquina inferior derecha, y va solo hacia la derecha o hacia abajo. Además, una ruta válida no puede pasar por un obstáculo. Aquí hay algunos ejemplos dibujados con +caracteres:

Valid path  Invalid path  Invalid path  Invalid path
++........   ++........    +++++.....    ..+.......
.++++++#..   .+.....#..    ....+++#++    ..++...#..
......+#..   .+.++++#..    .......#.+    ...+++.#..
....#.++++   .+++#.++++    ....#....+    ....#+....

Dos caminos son esencialmente similares ¹ si uno puede transformarse en el otro moviendo uno +a la vez. Las rutas intermedias también deben ser válidas, por lo que no puede doblar una ruta sobre un obstáculo. Por ejemplo, los primeros dos caminos aquí son esencialmente similares, pero el tercero es esencialmente diferente de ellos, ya que no se puede mover sobre los dos obstáculos:

++........   +.........   +++++++++.
.+++++.#..   ++.....#..   .......#+.
.....+.#..   .++++++#..   .......#++
....#+++++   ....#.++++   ....#....+

Salida

Su salida es el número de caminos esencialmente diferentes a través de la carrera de obstáculos. En otras palabras, si todas las rutas válidas se dividen en clases de rutas esencialmente similares, la salida es el número de clases. Tenga en cuenta que este número puede ser 0, si no hay rutas válidas.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten. No hay límites de tiempo, excepto que debe evaluar su programa en cada caso de prueba antes de enviarlo.

Casos de prueba

....
....
.... => 1

...#
....
...# => 0

#..#
..#.
.... => 0

......
......
..##..
......
...... => 2

......
...#..
......
..#...
#..... => 3

......
..#...
......
....#.
#..... => 4

.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0

......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7

.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17

..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10

.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16

_{1 El término técnico correcto es "homotópico" .}

Caracoles , 53 49 bytes

A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

Por una vez, no tuve que usar tla temida instrucción de teletransporte. Como resultado, los casos de prueba terminan instantáneamente en lugar de tomar eones.

Sin golf:

A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

Las opciones A^significan comenzar en la esquina superior izquierda y contar todas las rutas coincidentes. La idea principal es verificar una condición de canonicidad para los caminos. Sinceramente, no esperaba que funcionara, pero resolvió los casos de prueba, así que ... Lo que intenta verificar es que, dentro de la ruta actual, se haya seleccionado la ruta más codiciosa, es decir, ir a la derecha tantas veces como sea posible. , hacia abajo tantas veces como sea posible, etc. sin cruzar ningún obstáculo. Esto se hace comprobando, después de moverse hacia la derecha 1 o más veces y luego hacia abajo 1 o más veces, que no se pudo alcanzar el siguiente cuadrado (que debe estar a la derecha) yendo a la derecha una vez más en el segmento anterior hacia la derecha. La condición análoga también se verifica después de moverse hacia la derecha y luego hacia abajo.

Python 2, 170 131 112 bytes

def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

Una función, ftomar la carrera de obstáculos como una lista de filas y devolver el número de caminos esencialmente diferentes.

Explicación

El concepto básico es el siguiente: Elegimos un cierto obstáculo, o , de modo que no haya otros obstáculos en el cuadro que limita o y la esquina superior izquierda.

+--+....
|..|....  
+--#<==== o
.....#..
.#......
........

Luego consideramos los dos sub-cursos al este y al sur de o . Sólo tenemos en cuenta ninguno de estos sub-campos si o realmente se puede cruzar desde una dirección que conduce a ellos, es decir, cruzaron desde el norte hasta llegar al este, y cruzaron desde el oeste para llegar al sur. Resolvemos el problema para cada uno de los sub-cursos seleccionados y devolvemos la suma de los resultados. Estos números corresponden al número de caminos esencialmente diferentes al cruzar o desde la izquierda y desde la derecha, respectivamente, por lo tanto, los dos conjuntos de caminos resultantes son esencialmente diferentes. Dado que no hay obstáculos entre el punto de partida y o, hay una ruta entre el punto de partida y cualquier punto de entrada en cada una de estas regiones, y todas esas rutas que conducen al mismo punto son esencialmente similares, por lo tanto, la suma anterior es el número completo de rutas esencialmente diferentes en todo el curso.

                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/       
////////       

Las cosas son un poco complicadas por el hecho de que la carrera de obstáculos por sí sola no transmite toda la información necesaria. Por ejemplo, considere el curso B en el diagrama anterior. Tomados por sí mismos, no podemos determinar si cada uno de los obstáculos se puede cruzar desde el norte. Si B fuera el curso de entrada, entonces, dado que todos los caminos comienzan en la esquina superior izquierda, ninguno de los obstáculos podría haber sido cruzado desde el norte, pero, dado que podemos llegar a B desde cualquier lado del obstáculo izquierdo al cruzar o desde el este , debemos tratar este obstáculo como si se pudiera cruzar desde el norte al resolver el recorrido; Sin embargo, lo mismo no es válido para el obstáculo correcto, que no se puede cruzar desde esta dirección.

Descubrimos esta información adicional al especificar, junto con la carrera de obstáculos, el número de caracteres a lo largo de la primera fila, comenzando desde la izquierda, en los que el camino puede comenzar. En el diagrama anterior, esto se representa como la línea continua al lado de cada curso. Si bien, técnicamente, también debemos especificar el número correspondiente de caracteres a lo largo de la primera columna en la que puede comenzar la ruta, como en el caso del subcampo A , en la práctica siempre seleccionamos el obstáculo más alto, por lo que esta información no es necesaria .

La selección real de o es la siguiente: pretendemos que a cada fila, que no sea la última, le sigue un obstáculo (es decir, tiene un #anexo), y seleccionamos el primer obstáculo en el curso resultante, en orden de lectura. Para las filas (que no sean las últimas) que originalmente no tenían ningún obstáculo, esto significa efectivamente que las omitimos (al tiempo que observamos que la ruta a continuación puede comenzar en cualquier personaje a lo largo de la fila superior). Eventualmente, terminamos con un curso que tiene una sola fila sin obstáculos, para el cual solo hay un camino posible.

CJam, 85 84 82 81 80 79 bytes

qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Pruébalo en línea. O ejecute todo el conjunto de pruebas.

La eficiencia de esta solución es probablemente bastante horrible, pero resuelve cada caso de prueba en unos pocos segundos.

Explicación

Tendré que agregar un desglose completo del código más tarde, pero la idea algorítmica es esta:

• Deje que el ancho y la altura de la cuadrícula sean Wy H, respectivamente.
• Generamos todas las rutas posibles como las permutaciones distintas de W-1copias 0y H-1copias de W-1(donde 0representa un paso horizontal y W-1un paso vertical). Recorremos todos esos caminos tomando repetidamente el primer elemento de la cuadrícula y luego omitiendo las stepceldas en el orden de lectura (donde stepestá 0o W-1). Descartamos todos los caminos que contienen a #.
• Luego, eliminamos repetidamente un grupo de rutas similares (que serán todas las rutas similares a la primera de las rutas restantes). La búsqueda de rutas similares se vuelve un poco más fácil al relajar ligeramente la condición: en lugar de verificar si uno se xha movido, verificamos si las rutas difieren exactamente en dos lugares. Si ese es el caso, esos dos lugares tendrán un movimiento vertical y horizontal intercambiados. Esto hace que todo el segmento entre esos movimientos se desplace diagonalmente por una celda. Pero si ambos caminos son válidos, desplazar cualquier parte del camino por una celda en diagonal no puede cruzar un obstáculo, por lo que son similares. Todavía necesitamos encontrar el cierre transitivo, así que seguimos haciéndolo hasta que no encontremos más caminos similares antes de pasar al siguiente grupo.
• Finalmente, contamos los grupos que hemos encontrado, que dejamos en la parte inferior de la pila.