Number-Connect-Spiel in C/C++?

Spiel – Angenommen, es gibt ein n × n-Quadrat-Array. Unter ihnen sind einige Quadrate leer, einige sind fest und einige nicht feste Quadrate sind durch die ganzen Zahlen 1, 2, 3, ... festgelegt. Jede ganze Zahl enthält oder besetzt genau zwei verschiedene Felder auf der Tafel. Die Aufgabe des Spielers besteht darin, die beiden Vorkommen jeder Ganzzahl auf dem Spielbrett mithilfe einfacher Pfade zu verbinden, die ausschließlich horizontale und vertikale Bewegungen ausführen. Zwei unterschiedliche Wege dürfen sich nicht kreuzen. Kein Pfad darf feste Blöcke enthalten (solide Blöcke sind auf keinem Pfad zulässig). Schließlich müssen alle nicht durchgezogenen Quadrate durch Pfade gefüllt werden.

Algorithmus – Um ein effizientes Zufallsrätsel mit einer gegebenen Brettgröße n × n zu konstruieren, generieren wir zunächst zufällige einfache, voneinander disjunkte Pfade auf der Tafel. Wenn einige isolierte Blöcke noch außerhalb aller generierten Pfade liegen, markieren Sie diese isolierten Blöcke als fest (verboten). Als nächstes geben wir die Endpunkte des Pfades und eine Liste ausgefüllter Quadrate als Puzzle an.

Also generieren wir zunächst eine Lösung und berechnen dann das Rätsel auf Grundlage dieser Lösung. Pfade und ausgefüllte Quadrate trennen n × n Platten. Wir implementieren und finden die Datenstruktur, um diese Partition zu generieren. Die Datenstruktur verarbeitet eine Teilmenge der Menge von n^2 Feldern auf dem Schachbrett.

Pseudocode

• Positionieren Sie die Quadrate (a, b) und (c, d) zufällig auf dem Schachbrett, sodass -

  • (a, b) und (c, d) einander benachbart sind, Und Weder

  • (a, b) noch (c, d) gehören zu irgendeinem bisher generierten Pfad. wenn drin Gesamtes Brett, gibt FAILURE /* zurück. Hier sind (a​​, b) und (c, d) die ersten beiden Felder auf dem neuen Pfad gründen. */

• Union zweier Union-Suchbäume, die enthält (a, b) und (c, d).

• Wiederholen, bis der aktuelle Pfad erweitert werden kann -

  Umbenennen (a, b) = (c, d).

Suchen Sie ein zufällig benachbartes Quadrat (c, d) (a, b), so dass -

• (c, d) zu keinem bisher generierten Pfad gehört (einschließlich des aktuellen Pfads)

• Der einzige Nachbar (c, d) auf dem aktuellen Pfad der Teilkonstruktion ist (a, b).

Wenn kein solcher Nachbar (c, d) gefunden wird, kann der Pfad nicht weiter verlängert werden, wodurch der Kreislauf unterbrochen wird

Ansonsten gehören die beiden (a, b) und (c, d) dazu und finde den Baum.

Setzen Sie die Endpunktflags der beiden Blöcke, die sich am Anfang und Ende des neuen Pfads befinden.

Zurück zum ERFOLG

Das obige ist der detaillierte Inhalt vonNumber-Connect-Spiel in C/C++?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!