Eingabe: ein Labyrinth, dargestellt durch eine beliebig große Matrix von Bools. (Außerhalb der Grenzen zählt als 0)
%Vor% Ausgabe: Eine gut aussehende Darstellung des Labyrinths (Nachbarschaft wird einem wchar_t zugeordnet):
Bearbeiten: Grundsätzlich wird jede 0 einem 4-Bit-Wert zugeordnet, der das Wandlayout darstellt.
Mein Ansatz und meine Gedanken:
Ich dachte, es wäre am einfachsten, jede Zelle gleichzeitig zu betrachten. Dann schauen Sie sich die Nachbarn an, um zu bestimmen, welche Art von Wert dort zu platzieren ist. Stellt sich heraus, ich habe 8 boolesche Eingaben (alle Nachbarn), dies erzeugt 2 ^ 8 = 256 verschiedene Szenarien. Ich habe nicht das Gefühl, sie alle hart zu codieren.
Gibt es eine elegantere Möglichkeit, die Werte korrekt zuzuordnen?
Inspiriert von Doug T. Lösung Ich habe selbst folgendes geschrieben.
Im Grunde laufe ich zweimal durch die Matrix (schlechte Leistung: /). Das erste Mal, wenn ich Wände um jede 1 in der Matrix zeichne, mache ich das mit Bitmasken. Das zweite Mal räume ich alle "nach innen zeigenden" Wände auf.
Beispieleinrichtung:
%Vor%Die Mauerschleife:
%Vor%Die Reinigungsschleife:
%Vor%Ich habe dann eine 16 Größe (eine für jedes Symbol) Lookup-Liste mit einem Eintrag für jedes Zeichen.
%Vor%Dieser Algorithmus ist auf keinen Fall effizient, O (2 * width * height) ist nicht gut ... Er kann verbessert werden, indem eine 256 group loop-up Tabelle erzeugt wird, wie andere vorgeschlagen haben, dies würde uns O ( 1) bei der Ausführung.
Ich habe dies in meinem erfolgreichen Beitrag für das IOCCC 2004 umgesetzt. Ich bin mir sicher, dass Sie den Code gut dokumentiert und leicht nachvollziehbar finden.
Wenn Sie nur die Antwort wollen, so wie ich mich erinnere, bestand die Herangehensweise darin, eine Bitmap von besetzten Zellen um jede Zelle zu berechnen und diese als Index in ein Array von Wandzeichen (oder äquivalent Glyphen) zu verwenden. Wenn Sie wie bei meiner Lösung keine Diagonalverschiebung zulassen, ist die Bitmap 4 Bit lang und das Array hat 2 ^ 4 = 16 Elemente. Wenn Sie eine Diagonalfahrt zulassen, benötigen Sie eine 8-Bit-Bitmap und 256 Einträge.
Sie können es winnowdown, indem Sie einige Zellen vor anderen ansehen, aber, ehrlich gesagt, 256 ist nicht so viele. Schreiben Sie ein Programm, das sie generiert oder manuell ausführt und eine Nachschlagetabelle verwendet. Die zusätzlichen 256 Byte (Sie können die Nachschlage-Map zu einem anderen Index machen, um das tatsächliche Zeichen zu erhalten) ist klein genug, um sich keine Gedanken zu machen.
Anstatt jede Zeile nach einer 1 zu durchsuchen und jede Zelle zu zeichnen, könnten Sie die Wände "laufen".
nicht am Ende Ihres Bool-Arrays:
Definieren Sie eine Funktion namens "Draw", die:
- Nach der Rückkehr den Scan fortsetzen, bis das nächste 1 oder Ende der Eingabe gefunden wird.
Vielleicht nicht der effizienteste, aber Sie sagten elegant. Rekursion ist immer elegant! (bis Sie einen Stackoverflow bekommen).
Hier ist ein gehackter Code (benutze keine magischen Zahlen wie ich :)), um dir zu helfen:
%Vor%In der obigen Lösung zeichne ich nur '*' s. Wenn Sie jedoch ein bestimmtes Stück für eine bestimmte Situation zeichnen wollten, würde ich eine Nachschlagetabelle verwenden, wie walkytalky in seinem Kommentar sagte. Ordnen Sie einem gegebenen Stück eine gegebene Menge von benachbarten 1 und 0 zu. IE:
Nachschlagen:
%Vor%würde ein "T" Ergebnis für das mittlere Wandstück ergeben. Achten Sie darauf, "aus der Karte" gleichwertig mit 0 zu behandeln.
Wenn alles gesagt und getan ist, ist vielleicht nur ein gerader Scan mit einer Nachschlagetabelle basierend auf benachbarten Teilen (ohne Rekursion) die beste Wahl, es sei denn, Sie können die obige Lösung schlauer machen, wenn Sie nicht erneut scannen, was bereits gescannt wurde.
> Führe zuerst die Matrix durch und füge die folgende Kernel-Matrix hinzu, zentriere die 0 des Kernels auf jedem 1 und füge die Zahlen den benachbarten Quadraten hinzu (das heißt, mache eine binäre Darstellung aller Nachbarn).
Dann schreibe einfach die Liste der Regeln, eine Regel für jede Form , keine Regel für jede mögliche Summe. Zum Beispiel
%Vor%oder was immer du willst.
Wenn Sie zuerst feststellen, welche Kacheln Wände sind, dann kodieren Sie einen speziellen Fall für jeden Wandtyp, den Sie haben, wie vertikal, wenn es einen links und / oder rechts gibt, aber keinen oben oder unten / p>
Das sollte es ein wenig eingrenzen, hoffe ich. :) vertikal, horizontal und vier verschiedene Kanten. Das sind 6 Fälle, sobald Sie erkannt haben, welche überhaupt Kanten sind.
Weniger als 256 mindestens. :)
Nur ein schneller Hack. Mit einem 3x3-Array und einer Modulo-Arithmetik könnten Sie wahrscheinlich die Anzahl der Speicherzugriffe um ein Vielfaches verringern, aber es könnte hässlich aussehen. Warnung Ich habe es nicht über einen Compiler laufen lassen, so dass es Tippfehler enthalten kann.
%Vor%