Dada uma grade de direções e uma posição inicial e final, determine o número mínimo de substituições na grade de direção que precisam ser feitas para concluir o caminho entre os dois pontos. A grade é duplamente cilíndrica. Isso é mais claro, dado um exemplo.

Exemplo

Vamos pegar a seguinte grade como exemplo:

>>>>v
>>>><
<<<<<

Vamos começar em (1, 1)e terminar em (1, 3)(onde estão as coordenadas (x, y)ou (col, row), com a linha superior e a coluna esquerda 1). Então, uma solução possível é substituir (1, 1)e (1, 2)por v, para que a grade final fique assim:

v>>>v
v>>><
<<<<<

A partir de (1, 1), o caminho nos levaria a (1, 3). No entanto, existe uma solução mais curta, que é substituir (5, 2)por v, portanto, a grade final é esta:

>>>>v
>>>>v
<<<<<

A partir de (1, 1), um caminho bastante longo leva a (1, 3).

Substituir qualquer coisa na linha superior por ^obras também (obrigado @Spitemaster).

Entrada

A entrada consistirá em uma grade retangular de 4 valores possíveis, além de duas coordenadas. Você pode pegar a grade em qualquer formato razoável; por exemplo, matriz de caracteres ou número inteiro, lista de cadeias, etc. Você também pode solicitar as dimensões da grade. Você pode pegar as coordenadas em qualquer formato razoável; por exemplo, par inteiro, número complexo, etc. Você pode escolher a indexação 0 ou 1.

Resultado

A saída deve ser um número inteiro único, o número mínimo de substituições de grade necessárias para fechar o caminho do início ao fim.

Regras e especificações

• As brechas padrão se aplicam
• a grade é duplamente cilíndrica, o que significa que subir do topo vai para o fundo, da esquerda para a esquerda, para a direita etc.

Casos de amostra

Os casos de amostra são dados como uma matriz de caracteres e coordenadas 1-indexadas.

Caso 1

Entrada

>>>>v
>>>><
<<<<<
1 1
1 3

Resultado

1

Explicação

Consultar exemplo.

Caso 2

Entrada

<<<<<
v>v>v
>>>>>
1 1
5 3

Resultado

1

Explicação

Você pode substituir (1, 1)por vou (2, 1)com v. No primeiro caso, a partir de (1, 1), o caminho segue direto para a direita e para o destino. No segundo caso, o caminho sai da esquerda para a direita, alcança (2, 1), desce, direita, desce e depois para a direita até atingir o destino.

Caso 3

Entrada

^^^^^^
><<>>>
vvvvvv
2 2
5 2

Resultado

2

Explicação

A melhor mudança é fazer a linha central dobrar da esquerda para o ponto; ou seja, crie o primeiro e o último itens na linha central <. Alternativamente, faça 2 2e 3 2ambos >.

Este é um desafio do código-golfe , portanto o código mais curto vence!

JavaScript (ES6),  140  135 bytes

Toma entrada como (a, width, height, x1, y1)(x0, y0)onde a[]é uma matriz de números inteiros e todas as coordenadas são 0-indexado.

$-2$$-1$$0$$1$

(a,w,h,X,Y)=>m=g=(x,y,n=0,r=a[y%=h],v=r[x%=w])=>x-X|y-Y?[-1,0,1,2].map(d=>r[v<2&&g(x+w+d%(r[x]=2),y+h+--d%2,n+(v!=d)),x]=v)|m:m=m<n?m:n

Experimente online!

Quão?

$(x,y)$$(X,Y)$

$n$

$m$$n$

Geléia , 73 72 bytes

W,0+Ɱ⁴PṬ€×Ɱ3¤Ẏ¤,€ɗ/€Ẏ$‘ƭ€ịØ.,N;U$¤;ɗ/0ị+æ.Ɱ⁴‘Ṫịʋ¥Ɗ%⁴ṭƲ⁴P¤¡ŒHṪe¥/Ʋ€Ẹ¬Ɗ/¿Ṫ

Experimente online!

Exemplo usando o caso 3 que requer duas alterações (também possui um rodapé para converter os ><v^números em números).

Um programa completo que espera os seguintes argumentos:

• Esquerda: uma lista de duas listas; primeiro, a grade de direção nivelada codificada como 1 = direita, 2 = esquerda, 3 = abaixo, 4 = acima, seguida por uma lista da posição final e da posição inicial como índices zero [linha, coluna]. Para o primeiro exemplo [1,1,1,1,3,1,1,1,1,4,2,2,2,2,2],[[2,0],[0,0]],.

• Direita: uma lista do número de linhas seguidas por colunas. Para o primeiro exemplo[3,5]

Retorna o número de alterações necessárias para obter do início ao fim. Retarde uma vez que isso é mais de uma alteração. No TIO, o terceiro exemplo de caso leva aprox. 30 segundos para concluir.

Explicação completa abaixo, mas a visão geral é:

1. Inicialize um contador para zero.
2. $\mathit{row} × \mathit{column}$
3. Verifique se a posição final está incluída:
   • $3 × \mathit{row} × \mathit{column}$
   • Se verdadeiro, encerre e envie o contador

Explicação completa:

W,0 | Wrap input in a list, and then pair with 0 (thus initialising the counter)


                                           Ɗ/¿ | While the following is true for the first item of the input pair (i.e. the list of all grids to be tested, paired with the end and start grid positions):
                                       Ʋ€      | - For each member of the list:
          ɗ/                                   |   - Reduce using the following as a dyad (so left argument is flattened grid and right is end/start positions)
ị       ¤                                      |     - Index into the following as a nilad
 Ø.                                            |       - [0, 1]
   ,N                                          |       - Pair with negative [[0, 1], [0, -1]]
     ;U$                                       |       - Concatenate to upended version of this [[0, 1], [0, -1], [1, 0], [-1, 0]]
         ;                                     |     - Concatenate (to end/start positions)
                            Ʋ⁴P¤¡              |   - Repeat the following links the number of times indicated by the product of the grid dimensions:
                        Ɗ                      |     - Following as a monad:
            0ị                                 |       - Last item (current grid position)
              +        ¥                       |       - Add to the following as a dyad:
               æ.Ɱ⁴                            |         - Dot product of current position with each of grid dimensions
                   ‘                           |         - Increase by 1
                    Ṫ                          |         - Tail (which is current position in flattened grid)
                     ị                         |         - index into flattened grid
                         %⁴                    |        - Mod grid dimensions
                           ṭ                   |        - Tack onto end of current grid/position list
                                 ŒH            |   - Split into halves (first half will be flattened grid and desired end position, second half will be all positions reached after moving through grid)
                                     ¥/        |   - Following as a dyad, with the first half from above step as left argument and the second half as right
                                   Ṫ           |     - Tail (i.e. the desired end position)
                                    e          |     - Exists within (the list of all positions reached)
                                         Ẹ¬    | - Not true for any of the input grids


                    ƭ€ | For each of the pair (list of grids, counter), do one of the following:
                  $    | - For the list of grids, do the following as a monad:
              ɗ/€      |   - Do the following as a dyad, with the flattened grid as the left argument and end/start positions as the right:
+Ɱ                     |     - Add to the flattened grid list each of:
           ¤           |       - The following as a nilad
         ¤             |         - The following as a nilad:
  ⁴P                   |           - The product of the grid dimensions
    Ṭ€                 |           - Convert each (using an implicit range from 1 to the grid dimension product) to a boolean list with a 1 at the relevant position (i.e. [[1], [0, 1], [0, 0, 1]...])
      ×Ɱ3              |           - Multiply by each of 1..3
          Ẏ            |        - Flatten to a single list of lists
            ,€         |    - Pair each with the end/start positions
                 Ẏ     |   - Tighten to a single list of grids paired with end/start positions
                   ‘   | - For the counter increment it


Ṫ | Finally, take the tail (which is the final value of the counter)