Bestimmen Sie anhand eines Richtungsgitters sowie einer Start- und Endposition die Mindestanzahl von Ersetzungen im Richtungsraster, die vorgenommen werden müssen, um den Pfad zwischen den beiden Punkten zu vervollständigen. Das Gitter ist doppelt zylindrisch. Dies wird anhand eines Beispiels klarer.

Beispiel

Nehmen wir als Beispiel das folgende Raster:

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

Beginnen wir bei (1, 1)und enden bei (1, 3)(wo die Koordinaten sind (x, y)oder (col, row), wobei die obere Zeile und die linke Spalte sind 1). Eine mögliche Lösung besteht darin, das (1, 1)und (1, 2)durch zu ersetzen v, sodass das endgültige Raster folgendermaßen aussieht:

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

Ausgehend von (1, 1)würde uns der Weg führen (1, 3). Es gibt jedoch eine kürzere Lösung, die ersetzt (5, 2)werden vmuss. Das endgültige Raster lautet also:

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

Ausgehend von (1, 1)führt ein ziemlich langer Weg zu (1, 3).

Das Ersetzen von allem in der obersten Reihe durch ^funktioniert auch (danke @Spitemaster).

Eingang

Die Eingabe besteht aus einem rechteckigen Raster mit 4 möglichen Werten sowie zwei Koordinaten. Sie können das Raster in jedem vernünftigen Format verwenden. Beispiel: Zeichen- oder Ganzzahlmatrix, Zeichenfolgenliste usw. Sie können auch die Abmessungen des Rasters anfordern. Sie können die Koordinaten in jedem vernünftigen Format verwenden. Beispiel: Ganzzahlpaar, komplexe Zahl usw. Sie können zwischen 0- und 1-Indizierung wählen.

Ausgabe

Die Ausgabe sollte eine einzelne Ganzzahl sein, die minimale Anzahl von Gitterersetzungen, die erforderlich sind, um den Pfad vom Anfang bis zum Ende zu schließen.

Regeln und Spezifikationen

• Standardschlupflöcher gelten
• Das Gitter ist doppelt zylindrisch, was bedeutet, dass die Bewegung von oben nach unten, von links nach links nach rechts usw. erfolgt.

Beispielfälle

Die Beispielfälle werden als Zeichenmatrix und 1-indizierte Koordinaten angegeben.

Fall 1

Eingang

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

Ausgabe

1

Erläuterung

Siehe Beispiel.

Fall 2

Eingang

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

Ausgabe

1

Erläuterung

Sie können entweder (1, 1)mit voder (2, 1)mit ersetzen v. Im ersten Fall (1, 1)geht der Pfad ausgehend geradeaus und dann rechts zum Ziel. Im zweiten Fall schlängelt sich der Pfad von links nach rechts, erreicht (2, 1), geht nach unten, rechts, unten und dann nach rechts, bis er das Ziel erreicht.

Fall 3

Eingang

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

Ausgabe

2

Erläuterung

Die beste Änderung besteht darin, die mittlere Reihe links bis zum Punkt zu wickeln. Das heißt, machen Sie das erste und letzte Element in der mittleren Reihe <. Alternativ machen 2 2und 3 2beides >.

Dies ist eine Code-Golf- Herausforderung, also gewinnt der kürzeste Code!

JavaScript (ES6),  140  135 Byte

Nimmt die Eingabe als (a, width, height, x1, y1)(x0, y0)wo a[]ist eine Matrix von ganzen Zahlen und alle Koordinaten sind 0-indiziert.

Wegbeschreibung: für links , für oben , für rechts und für unten .$-2$- 1 0 1$-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

Probieren Sie es online aus!

Wie?

Wir verwenden eine Breitensuche, um alle möglichen Pfade von nach auszuprobieren ohne zweimal dieselbe Zelle zu besuchen.$(x,y)$$(X,Y)$

Wir verfolgen, wie oft die gewählte Richtung nicht mit der in der Eingabematrix gespeicherten Richtung übereinstimmt.$n$

Wir geben schließlich , was als der Minimalwert von .$m$$n$

Gelee , 73 72 Bytes

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

Probieren Sie es online aus!

Beispiel mit Fall 3, der zwei Änderungen erfordert (hat auch eine Fußzeile, um die ><v^in Zahlen zu übersetzen ).

Ein vollständiges Programm, das die folgenden Argumente erwartet:

• Links: eine Liste von zwei Listen; Zuerst das abgeflachte Richtungsgitter, codiert als 1 = rechts, 2 = links, 3 = unten, 4 = oben, gefolgt von einer Liste der Endposition und Startposition als Nullindizes [Zeile, Spalte]. Zum ersten Beispiel [1,1,1,1,3,1,1,1,1,4,2,2,2,2,2],[[2,0],[0,0]].

• Rechts: Eine Liste der Anzahl der Zeilen, gefolgt von Spalten. Zum ersten Beispiel[3,5]

Gibt die Anzahl der Änderungen zurück, die erforderlich sind, um von Anfang bis Ende zu gelangen. Langsam, sobald dies mehr als eine Änderung ist. Bei TIO dauert der dritte Beispielfall ca. 30 Sekunden bis zum Abschluss.

Vollständige Erklärung unten, aber Übersicht ist:

1. Initialisieren Sie einen Zähler auf Null.
2. Berechnen Sie die Positionen nach jeder Bewegung von .$\mathit{row} × \mathit{column}$
3. Überprüfen Sie, ob die Endposition enthalten ist:
   • Wenn false, erhöhen Sie einen Zähler und erstellen Sie neue Versionen des Rasters, wobei jede einzelne Rasterposition in einen der drei möglichen alternativen Züge geändert wird. Kehren Sie dann zu Schritt 2 zurück.$3 × \mathit{row} × \mathit{column}$
   • Wenn true, beenden Sie den Zähler und geben Sie ihn aus

Vollständige Erklärung:

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)