. Schiebepuzzle

773. Schiebepuzzle

Schwierigkeit:Schwer

Themen:Array, Breitensuche, Matrix

Auf einem 2 x 3-Brett gibt es fünf Kacheln mit der Beschriftung 1 bis 5 und ein leeres Feld, das durch 0 dargestellt wird. Ein Zug besteht darin, 0 und eine in 4 Richtungen benachbarte Zahl zu wählen und diese zu vertauschen .

Der Zustand des Boards wird genau dann gelöst, wenn das Board [[1,2,3],[4,5,0]] ist.

Geben Sie bei gegebenem Puzzle-Brett die geringste Anzahl an Zügen zurück, die erforderlich sind, damit der Zustand des Bretts gelöst wird. Wenn es unmöglich ist, den Zustand der Platine zu lösen, geben Sie -1 zurück.

Beispiel 1:

• Eingabe:board = [[1,2,3],[4,0,5]]
• Ausgabe: 1
• Erklärung: Vertausche die 0 und die 5 in einem Zug.

Beispiel 2:

• Eingabe:board = [[1,2,3],[5,4,0]]
• Ausgabe: -1
• Erklärung: Keine Zahl von Zügen führt dazu, dass das Brett gelöst wird.

Beispiel 3:

• Eingabe:board = [[4,1,2],[5,0,3]]
• Ausgabe: 5
• Erklärung: 5 ist die kleinste Anzahl an Zügen, die das Spielbrett löst.
  • Ein Beispielpfad:
  • Nach Zug 0: [[4,1,2],[5,0,3]]
  • Nach Zug 1: [[4,1,2],[0,5,3]]
  • Nach Zug 2: [[0,1,2],[4,5,3]]
  • Nach Zug 3: [[1,0,2],[4,5,3]]
  • Nach Zug 4: [[1,2,0],[4,5,3]]
  • Nach Zug 5: [[1,2,3],[4,5,0]]

Einschränkungen:

• board.length == 2
• board[i].length == 3
• 0 <= Board[i][j] <= 5
• Jedes Value Board[i][j] ist einzigartig.

Hinweis:

1. Führen Sie eine Breitensuche durch, wobei die Knoten die Puzzlebretter und die Kanten sind, wenn zwei Puzzlebretter mit einem Zug ineinander umgewandelt werden können.

Lösung:

Wir können den Breadth-First Search (BFS)-Algorithmus anwenden. Die Idee besteht darin, alle möglichen Konfigurationen des Boards ausgehend vom gegebenen Anfangszustand Schritt für Schritt zu erkunden, bis wir den gelösten Zustand erreichen.

Ansatz:

1. Breitensuche (BFS):

   • BFS ist hier ideal, weil wir den kürzesten Weg zum gelösten Zustand suchen.
   • Jede Brettkonfiguration kann als Knoten betrachtet werden, und die Kanten zwischen Knoten stellen gültige Züge dar, bei denen die 0-Kachel mit einer benachbarten Kachel vertauscht wird.
   • Das BFS untersucht die Spielbrettkonfigurationen Ebene für Ebene und stellt sicher, dass wir mit der minimalen Anzahl an Zügen den gelösten Zustand erreichen.

2. Landesvertretung:

   • Wir stellen das Board als Zeichenfolge dar (zum einfacheren Vergleich und zur einfacheren Speicherung).
   • Der gelöste Zustand ist „123450“, da es sich um eine lineare Darstellung der Platine [[1,2,3],[4,5,0]] handelt.

3. Zustandsübergänge:

   • In jedem Bundesstaat kann das 0-Plättchen mit einem seiner 4 Nachbarn (oben, unten, links, rechts) ausgetauscht werden, sofern es sich innerhalb der Grenzen des Spielbretts befindet.

4. Verfolgung besuchter Staaten:

   • Wir müssen den Überblick über die besuchten Staaten behalten, um Zyklen und redundante Berechnungen zu vermeiden.

5. Überprüfung des gelösten Zustands:

   • Wenn die Spielbrettkonfiguration zu irgendeinem Zeitpunkt mit dem gelösten Zustand übereinstimmt, geben wir die Anzahl der Züge zurück, die erforderlich waren, um dorthin zu gelangen.

6. Umgang mit unmöglichen Fällen:

   • Wenn BFS abgeschlossen ist und wir den gelösten Status nicht finden, bedeutet das, dass es unmöglich ist, das Rätsel zu lösen, und wir geben -1 zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 773. Schiebepuzzle

  
  
  Erläuterung:




Ersteinrichtung: Wir beginnen mit der Umwandlung der 2D-Platine in eine 1D-Leiste zur einfacheren Handhabung.

BFS-Ausführung: Wir stellen den Anfangszustand des Boards zusammen mit der Anzahl der Züge (beginnend bei 0) in die Warteschlange. In jeder BFS-Iteration untersuchen wir die möglichen Bewegungen (basierend auf der Position der 0-Kachel), tauschen 0 mit benachbarten Kacheln und stellen die neuen Zustände in die Warteschlange.

Besuchte Staaten: Wir verwenden ein Wörterbuch, um die besuchten Board-Staaten zu verfolgen, um ein erneutes Besuchen und Zurückkehren zu denselben Staaten zu vermeiden.

Kantenvalidierung: Wir überprüfen, ob jede Bewegung innerhalb der Grenzen des 2x3-Rasters bleibt, insbesondere stellen wir sicher, dass keine illegalen Bewegungen stattfinden, die das Raster umkreisen (z. B. Bewegung nach links am linken Rand oder nach rechts am rechten Rand). 

Ergebnis zurückgeben: Wenn wir den Zielzustand erreichen, geben wir die Anzahl der Züge zurück. Wenn BFS abgeschlossen ist und wir das Ziel nicht erreichen, geben wir -1 zurück.



  
  
  Zeitkomplexität:




BFS-Komplexität: Die zeitliche Komplexität von BFS beträgt O(N), wobei N die Anzahl der eindeutigen Platinenzustände ist. Für dieses Rätsel gibt es höchstens 6! (720) mögliche Konfigurationen.



  
  
  Raumkomplexität:



Die Raumkomplexität ist aufgrund des Speicherbedarfs für die Warteschlange und die besuchten Zustände ebenfalls O(N).


Diese Lösung sollte angesichts der Einschränkungen effizient genug sein.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt von. Schiebepuzzle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!