fundo

Eu construí uma pista de obstáculos simples colocando caixas em uma sala retangular. Agora, quero contar o número de maneiras essencialmente diferentes pelas quais ele pode ser resolvido. Eu preciso que você me escreva um programa para isso.

Entrada

Sua entrada é uma matriz retangular não vazia dos caracteres .#. Os pontos .são espaços vazios e os #obstáculos.

Um caminho através da pista de obstáculos começa no canto superior esquerdo e termina no canto inferior direito, e vai apenas para a direita ou para baixo. Além disso, um caminho válido não pode passar por um obstáculo. Aqui estão alguns exemplos desenhados com +-characters:

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

Dois caminhos são essencialmente similares ¹ se um pode ser transformado no outro movendo um de +cada vez. Os caminhos intermediários também devem ser válidos, para que você não possa dobrar um caminho sobre um obstáculo. Por exemplo, os dois primeiros caminhos aqui são essencialmente semelhantes, mas o terceiro é essencialmente diferente deles, pois não pode ser contornado pelos dois obstáculos:

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

Saída

Sua saída é o número de caminhos essencialmente diferentes através da pista de obstáculos. Em outras palavras, se todos os caminhos válidos forem divididos em classes de caminhos essencialmente similares, a saída será o número de classes. Observe que esse número pode ser 0, se não houver caminhos válidos.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas. Não há limites de tempo, exceto que você deve avaliar seu programa em todos os casos de teste antes de enviá-lo.

Casos de teste

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

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

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

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

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

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

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

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

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

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

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

_{1 O termo técnico correto é "homotópico" .}

Caracóis , 53 49 bytes

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

Pela primeira vez, não precisei usar ta temida instrução de teleporte. Como resultado, os casos de teste terminam instantaneamente, em vez de levarem eras.

Ungolfed:

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

As opções A^significam começar no canto superior esquerdo e contar todos os caminhos correspondentes. A idéia principal é verificar uma condição de canonicidade para os caminhos. Sinceramente, não esperava que funcionasse, mas acertou os casos de teste, então .... O que ele tenta verificar é que, dentro do caminho atual, a rota mais gananciosa foi selecionada, ou seja, indo o mais rápido possível , descer o maior número de vezes possível, etc. sem atravessar obstáculos. Isso é feito verificando, depois de mover para a direita 1 ou mais vezes e, em seguida, para baixo 1 ou mais vezes, que o próximo quadrado (que deve estar à direita) não poderia ter sido atingido, indo à direita mais uma vez no segmento anterior anterior. A condição análoga também é verificada depois de se mover para a direita e depois para baixo.

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))

Uma função, ftomando a pista de obstáculos como uma lista de linhas e retornando o número de caminhos essencialmente diferentes.

Explicação

O conceito básico é este: escolhemos um certo obstáculo, o , de modo que não haja outros obstáculos na caixa que delimita oe no canto superior esquerdo.

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

Consideramos então os dois subcursos a leste e ao sul de o . Consideramos apenas um desses subcursos se o pode realmente ser cruzado a partir de uma direção que os leva, ou seja, cruzado do norte para o leste e cruzado do oeste para o sul. Resolvemos o problema para cada um dos sub-cursos selecionados e retornamos a soma dos resultados. Esses números correspondem ao número de caminhos essencialmente diferentes ao cruzar o da esquerda e da direita, respectivamente, portanto, os dois conjuntos de caminhos resultantes são essencialmente diferentes. Como não há obstáculos entre o ponto de partida e o, existe um caminho entre o ponto inicial e qualquer ponto de entrada em cada uma dessas regiões e todos os caminhos que levam ao mesmo ponto são essencialmente semelhantes; portanto, a soma acima é o número completo de caminhos essencialmente diferentes em todo o percurso.

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

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

As coisas são um pouco complicadas pelo fato de que a pista de obstáculos por si só não transmite todas as informações necessárias. Por exemplo, considere o curso B no diagrama acima. Por si só, não podemos determinar se cada um dos obstáculos pode ser atravessado a partir do norte. Se B fosse o percurso de entrada, então, como todos os caminhos começam no canto superior esquerdo, nenhum obstáculo poderia ter sido atravessado do norte, mas, como podemos alcançar B de ambos os lados do obstáculo esquerdo ao cruzar o leste , devemos tratar esse obstáculo como se ele pudesse ser atravessado do norte ao resolver o percurso; o mesmo não se aplica ao obstáculo certo, no entanto, que não pode ser cruzado nessa direção.

Conversamos essas informações extras especificando, juntamente com a pista de obstáculos, o número de caracteres ao longo da primeira linha, começando pela esquerda, em que o caminho pode começar. No diagrama acima, isso é representado como a linha sólida ao lado de cada percurso. Enquanto, tecnicamente, também precisamos especificar o número correspondente de caracteres ao longo da primeira coluna em que o caminho pode começar, como no caso do subcurso A , na prática sempre selecionamos o maior obstáculo, portanto, essas informações não são necessárias. .

A seleção real de o é a seguinte: fingimos que cada linha, exceto a última, é seguida por um obstáculo (ou seja, tem um #anexo) e selecionamos o primeiro obstáculo no curso resultante, em ordem de leitura. Para linhas (além da última) que não apresentavam obstáculos originalmente, isso significa efetivamente que as ignoramos (observando que o caminho abaixo pode começar com qualquer caractere na linha superior). Eventualmente, terminamos com um percurso que possui uma única linha sem obstáculos, para o qual existe apenas um caminho possível.

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;],

Experimente online.Ou execute todo o conjunto de testes.

A eficiência desta solução é provavelmente bastante horrível, mas resolve cada caso de teste em alguns segundos.

Explicação

Vou ter que adicionar uma análise completa do código mais tarde, mas a ideia algorítmica é esta:

• Seja a largura e a altura da grade WeH , respectivamente.
• Geramos todos os caminhos possíveis como permutações distintas de W-1cópias 0e H-1cópias de W-1(onde 0representa um passo horizontal e W-1um passo vertical). Percorremos todos esses caminhos pegando repetidamente o primeiro elemento da grade e pulando as stepcélulas na ordem de leitura (onde stepé 0ou W-1). Descartamos todos os caminhos que contêm a #.
• Em seguida, removemos repetidamente um grupo de caminhos semelhantes (que serão todos os caminhos semelhantes ao primeiro dos caminhos restantes). A verificação de caminhos semelhantes fica um pouco mais fácil relaxando um pouco a condição: em vez de verificar se umx foi movido, verificamos se os caminhos diferem exatamente em dois lugares. Se for esse o caso, esses dois lugares terão um movimento vertical e horizontal trocado. Isso faz com que todo o segmento entre esses movimentos seja deslocado na diagonal por uma célula. Porém, se ambos os caminhos são válidos, mudar qualquer parte do caminho por uma célula na diagonal não pode atravessar um obstáculo; portanto, eles são semelhantes. Ainda precisamos encontrar o fechamento transitivo, por isso continuamos fazendo isso até não encontrarmos caminhos semelhantes antes de passar para o próximo grupo.
• Finalmente, contamos os grupos que encontramos, que deixamos na parte inferior da pilha.