[PYTHON] Ich habe mich im Labyrinth verlaufen
Guten Abend (* ´ω ｀) Vielen Dank für Ihre weitere Unterstützung.
Diesmal ist ein Labyrinth. Mal sehen, wie viele Züge Sie von Start bis Ziel benötigen.
Das Beispiellabyrinth unten Vielen Dank, dass Sie sich das Erbe eines Experten ausgeliehen haben m (_ _) m
maze.py
# "#"Ist eine Wand
# "S"Ist der Startpunkt,"G"Ist der Zielpunkt
# "."Ist die Art
maze = [
['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
]
Das obige hat ein Komma zwischen den Elementen, Es ist schwer zu verstehen, weil es Platz gibt. Lassen Sie uns das Display etwas verständlicher machen. Insbesondere habe ich versucht, es mit der folgenden Beschreibung erneut anzuzeigen.
maze.py
def print_maze(maze):
for xx in maze:
for yy in xx:
print(yy,end="")
print()
print_maze(maze)
#Ausführungsergebnis
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
Danach, während ich sage, dass ich mich im Labyrinth verlaufen werde, Es wird davon ausgegangen, dass die Koordinaten von Start und Ziel im Voraus bekannt sind.
maze.py
sx, sy = 0, 1 #Startpunktkoordinaten
gx, gy = 9, 8 #Zielpunktkoordinaten
Da es schwer vorstellbar ist, nur das oben erwähnte Labyrinth zu verwenden,
Immerhin werde ich das Labyrinth ordentlich umschreiben.
Schwarz wird die Wand sein, folgen Sie also der hellblauen Straße von "S" nach "G".
Grundsätzlich wählen wir die Koordinaten, die die "Straße" sein werden, aber es gibt einige Einschränkungen.
** 1. Ich kann nicht durch die Wand gehen ** ** 2. Die Straße, die Sie einmal genommen haben, kann niemals genommen werden **
1 scheint in Ordnung zu sein, wenn Sie die Zusammensetzung des Labyrinths kennen,
In Bezug auf 2 scheint es unmöglich, wenn Sie nicht notieren, wo Sie bestanden haben.
Sie benötigen also eine Notiz sowie eine Karte des Labyrinths, wie in der folgenden Abbildung gezeigt.
Ich werde überprüfen, wie viele Hände ich von Anfang an bis zum Ziel hatte
Notieren Sie sich die Zählnummer an den Koordinaten, die Sie gegangen sind, und fahren Sie fort.
Wenn Sie also die Nummer im Memo zurückgeben, wenn Sie das Ziel erreichen, ist die Mission beendet.
Es ist ein egoistisches Bild, aber ist es so?
Legen Sie fest, wie Sie vorgehen sollen
Ich möchte bis zur Erstellung eines Memos beschreiben.
maze.py
def print_maze(maze):
for xx in maze:
for yy in xx:
print(yy,end="")
print()
def make_memo():
none = None
field_x_length = len(maze[0]) #Anzahl der Elemente in x-Richtung
field_y_length = len(maze) #Anzahl der Elemente in y-Richtung
# [ None for i in range(4)]Wenn Sie so etwas versuchen, können Sie die Bedeutung der folgenden Beschreibung erkennen
distance = [[none for i in range(field_x_length)] for j in range(field_y_length)]
print_maze(distance)
maze = [
['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],# <== maze[0]
['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],# <== maze[1]
['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],# <== maze[2]
['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],# <== maze[3]
['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],# <== maze[4]
['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],# <== maze[5]
['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],# <== maze[6]
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],# <== maze[7]
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],# <== maze[8]
['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],# <== maze[9]
]
print_maze(maze)
make_memo()
Ausführungsergebnis.py
#Matze: print_maze(maze)
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
#Memo: make_memo()
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
Kommen wir nun zu den Feldern, die wir vorbereitet haben. !?
Ja, es ist ein Feld.
Wenn Sie ein Feld sagen, haben Sie natürlich Koordinaten, oder?
(Das? Ein bisschen gewaltsam !? (ﾟ Д ﾟ))
Ich habe versucht, die Koordinaten ein wenig zu schütteln.
Ohne Koordinaten können Sie nichts tun, um zu notieren, wo und wie Sie vorgehen sollen
Nun, es kann natürlich sein, zu definieren.
Der Rest ist die Richtung zu gehen. Wenn zum Beispiel → (rechts), ist es (x: 1, y: 0) unter Berücksichtigung der obigen Koordinaten, nicht wahr? Nachfolgend finden Sie eine Zusammenfassung der Vorgehensweise in alle vier Richtungen.
** → Rechts (x: 1, y: 0) ** ** ← Links (x: -1, y: 0) ** ** ↑ Oben (x: 0, y: -1) ** ** ↓ Unten (x: 0, y: 1) **
Wäre es nicht schön, wenn die Koordinaten, wenn alle oben genannten in der for-Anweisung von einem bestimmten Punkt aus gedreht wurden, die folgenden Bedingungen erfüllen?
- Keine Mauer
- Springen Sie nicht aus den definierten Koordinaten heraus
- Ein Ort, an dem ich noch nie gewesen bin
Lass es uns gleich schreiben !!
maze.py
for i in range(4):#Auf 4 setzen, um oben, unten, links und rechts anzugeben
#nx,ny :Zielkoordinaten, x,y :Aktuelle Koordinaten
nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i] # nx,ny = x + X[i], y + Y[i]Ist äquivalent zu
# i = 0 : nx , ny = x + 1, y + 0 ....→ Richtig(x: 1,y: 0)
# i = 1 : nx , ny = x + 0, y + 1 ....↑ Oben(x: 0,y:-1)
# i = 2 : nx , ny = x +-1, y + 0 ....← Links(x:-1,y: 0)
# i = 3 : nx , ny = x + 0, y +-1 ....↓ Unten(x: 0,y: 1)
# |←-----Springen Sie nicht aus der horizontalen Achse x heraus-----→| |←-----Springen Sie nicht aus der vertikalen Achse y heraus-----→|
if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length \
#|←-Die Mauer bricht nicht durch!-→| |←-----Erster Platz!------→|
and maze[nx][ny] != '#' and distance[nx][ny] == none):
#distance[x][y]:Aktueller Standort+Ein Wert von 1 ist die Entfernung[nx][ny]Hinweis an
distance[nx][ny] = distance[x][y] + 1
Der Rest beginnt von vorne bis Sie das Ziel erreichen Wenn Sie den obigen Vorgang wiederholen, wissen Sie, wie viele Züge Sie erreicht haben. Hass (...? Wie kontrollierst du es? .. ..
Wenn Sie in Schwierigkeiten sind, wie oben erwähnt
Bewegen Sie das, was Sie tun möchten (Programm), das Sie geschrieben haben, schnell
Lassen Sie uns die Operation zeichnen. Ich bin sicher, Sie werden sehen, was fehlt.
Hier gibt es kein Problem.
Bewegen wir uns von hier aus nach oben, unten, links und rechts.
Was sollten wir zu diesem Zeitpunkt angesichts der oben genannten Einschränkungen tun? .. ..
Versuchen wir es auf dem nächsten Feld nach oben, unten, links und rechts.
Oh! Ich habe mich in zwei Teile geteilt.
Es wurde notwendig, eine Verarbeitung durchzuführen, die sich in alle Richtungen an den Koordinaten von [0,1] und [2,1] bewegt.
Ist es möglich, den Zweig zu behandeln, indem jeder Fall gepuffert und verarbeitet wird?
Dieses Mal werden wir die Warteschlange verwenden. Dafür gibt es einen Grund.
Wenn im vorherigen Lassen Sie uns der Teilsumme ins Auge sehen ein Verzweigungspunkt erstellt wird,
Ich wählte einen der Pfade und ging bis zur Sackgasse (Suche nach Tiefenprioritäten).
Durch Ein- und Ausfasten der Koordinaten des Verzweigungspunkts als Warteschlange
Sie können beide Koordinaten des Verzweigungspunkts verarbeiten und dann die nächstniedrigere Ebene verarbeiten, oder?
Wie unten gezeigt, ist das Bild rot => blau => grün und jede Ebene wird verarbeitet und dann in Richtung der unteren Ebene verarbeitet.
Es scheint, dass dies als ** Breitenprioritätssuche ** bezeichnet wird.
Wenn Sie dagegen die Warteschlange in einen Stapel ändern, handelt es sich um eine Suche mit Tiefenpriorität.
Wenn es schwer zu verstehen ist oder wenn es falsch ist, kommentieren Sie bitte m (_ _) m
Nehmen wir an, Sie haben das Glück, das Ziel zu erreichen.
Ist es damals so?
** * Da es problematisch ist, ist nur der kürzeste Weg rot gestrichen. In der Realität wiederholen sich die Zweige, sodass die Quadrate auf der Straße (hellblau) rot werden sollten m (_ _) m **
Schauen Sie sich den grünen Rahmen in der oberen linken Abbildung an. Solange Sie kurz vor dem Ziel ankommen, müssen Sie natürlich nach rechts gehen, aber der Punkt ist ** Dies bedeutet, dass die Länge der in der Warteschlange gepufferten Daten auch kurz vor dem Ziel niemals 0 sein wird **. Aus dem Obigen wird der Prozess der Entscheidung über die Fahrtrichtung und das Fortfahren mit der while-Anweisung wiederholt. Sie müssen nur brechen, wenn Sie eine bestimmte Koordinate erreichen.
maze.py
def solve_maze(sx, sy, gx, gy, maze):
none = None
field_x_length = len(maze[0])
field_y_length = len(maze)
distance = [[none for i in range(field_x_length)] for j in range(field_y_length)]
buff = []#Pufferkoordinaten
buff.append([sx, sy])#Startkoordinaten hinzufügen
distance[sx][sy]=0#Schreiben Sie keine in den Startkoordinaten auf 0 um
while len(buff):# len(buff) ==Schleife bis 0
x,y = buff.pop(0)#Aktualisieren Sie Ihren aktuellen Standort
if x == gx and y == gy:#Pause, wenn Sie das Ziel erreichen
break
for i in range(4):
nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length \
and maze[nx][ny] != '#' and distance[nx][ny] == none):
buff.append([nx,ny])#Pufferkoordinaten, die wahrscheinlich vorrücken
distance[nx][ny] = distance[x][y] + 1
#Endergebnis des Memos anzeigen
print_maze(distance)
#Geben Sie zum Schluss das Memo des Zielpunkts zurück
return distance[gx][gy]
Ausführungsergebnis.py
#Memo-Ergebnis
None0NoneNoneNoneNoneNoneNone13None
212345None1312None
3None3NoneNone6NoneNone11None
4None4567891011
NoneNone5NoneNone8NoneNoneNoneNone
8767None9101112None
9NoneNoneNoneNoneNoneNoneNone13None
10111213None1716151415
11NoneNoneNoneNone18NoneNoneNone16
12131415None19202122None
#Entfernung zum Ziel
22
Es tut mir leid, es ist schwer zu verstehen, also werde ich es zeichnen.
Das Programm kann dies (..) φ Memo Memo
Ich habe gelernt ('◇') ゞ
Recommended Posts