[PYTHON] Je me suis perdu dans le labyrinthe
Bonsoir (* ´ω ｀) Merci pour votre soutien continu.
Cette fois, c'est un labyrinthe. Voyons combien de mouvements vous avez besoin du début au but
Exemple de labyrinthe ci-dessous Merci d'avoir emprunté l'héritage d'un expert m (_ _) m
maze.py
# "#"Est un mur
# "S"Est le point de départ,"G"Est le point de but
# "."Est la route
maze = [
['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
]
Ce qui précède a une virgule entre les éléments C'est difficile à comprendre car il y a de l'espace. Rendons l'affichage un peu plus facile à comprendre. Plus précisément, j'ai essayé de l'afficher à nouveau avec la description suivante.
maze.py
def print_maze(maze):
for xx in maze:
for yy in xx:
print(yy,end="")
print()
print_maze(maze)
#Résultat d'exécution
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
Après cela, en disant que je vais me perdre dans le labyrinthe, On suppose que les coordonnées de départ et d'objectif sont connues à l'avance.
maze.py
sx, sy = 0, 1 #Coordonnées du point de départ
gx, gy = 9, 8 #Coordonnées du point de but
Puisqu'il est difficile d'imaginer juste le labyrinthe mentionné ci-dessus
Après tout, je vais réécrire le labyrinthe proprement.
Le noir sera le mur, alors suivez la route bleu clair de "S" à "G".
En gros, on choisit les coordonnées qui seront la «route», mais il y a quelques mises en garde.
** 1. Je ne peux pas traverser le mur ** ** 2. La route que vous avez empruntée une fois ne peut jamais être prise **
1 semble être correct si vous connaissez la composition du labyrinthe,
Concernant 2, cela semble impossible à moins que vous ne notiez où vous êtes passé.
Vous devez donc avoir une note ainsi qu'une carte du labyrinthe, comme le montre la figure ci-dessous.
Je vais vérifier combien de mains j'ai eu du début au but, donc
Notez le nombre de comptage aux coordonnées de votre marche et continuez.
Par conséquent, si vous renvoyez le numéro dans le mémo lorsque vous atteignez l'objectif, la mission est terminée.
C'est une image égoïste, mais est-ce comme ça?
Mettez de côté comment procéder
Je voudrais décrire au point de faire une note.
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]) #Nombre d'éléments dans la direction x
field_y_length = len(maze) #Nombre d'éléments dans la direction y
# [ None for i in range(4)]Si vous essayez quelque chose comme ça, vous pouvez voir la signification de la description suivante
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()
Résultat d'exécution.py
#Labyrinthe: print_maze(maze)
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
#Note: make_memo()
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
NoneNoneNoneNoneNoneNoneNoneNoneNoneNone
Passons maintenant aux champs que nous avons préparés. !?
Oui, c'est un champ.
Quand vous dites un champ, bien sûr, vous avez des coordonnées, non?
(C'est? Un peu de force!? (ﾟ Д ﾟ))
J'ai essayé de secouer un peu les coordonnées.
Vous ne pouvez rien faire sans coordonnées pour noter où et comment procéder
Eh bien, il peut être naturel de définir.
Le reste est la direction à prendre. Par exemple, si → (à droite), c'est (x: 1, y: 0) compte tenu des coordonnées ci-dessus, n'est-ce pas? Voici un résumé de la façon de procéder dans les quatre directions.
** → Droite (x: 1, y: 0) ** ** ← Gauche (x: -1, y: 0) ** ** ↑ Ci-dessus (x: 0, y: -1) ** ** ↓ Ci-dessous (x: 0, y: 1) **
Ne serait-il pas bien si les coordonnées lorsque tout ce qui précède était activé dans l'instruction for à partir d'un certain point satisfont aux conditions suivantes?
- Pas un mur
- Ne sautez pas hors des coordonnées définies
- Un endroit où je n'ai jamais été
Écrivons-le tout de suite !!
maze.py
for i in range(4):#Réglez sur 4 pour spécifier haut, bas, gauche et droite
#nx,ny :Coordonnées de destination, x,y :Coordonnées actuelles
nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i] # nx,ny = x + X[i], y + Y[i]Est équivalent à
# i = 0 : nx , ny = x + 1, y + 0 ....→ Droite(x: 1,y: 0)
# i = 1 : nx , ny = x + 0, y + 1 ....↑ ci-dessus(x: 0,y:-1)
# i = 2 : nx , ny = x +-1, y + 0 ....← Gauche(x:-1,y: 0)
# i = 3 : nx , ny = x + 0, y +-1 ....↓ ci-dessous(x: 0,y: 1)
# |←-----Ne sautez pas de l'axe horizontal x-----→| |←-----Ne sautez pas de l'axe vertical y-----→|
if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length \
#|←-Le mur ne se brise pas!-→| |←-----Première place!------→|
and maze[nx][ny] != '#' and distance[nx][ny] == none):
#distance[x][y]:Localisation actuelle+Une valeur de 1 est la distance[nx][ny]Note à
distance[nx][ny] = distance[x][y] + 1
Le reste commence du début jusqu'à ce que vous atteigniez l'objectif Si vous répétez le processus ci-dessus, vous saurez combien de coups vous avez atteint l'objectif. Déteste (...? Comment le contrôlez-vous? .. ..
En cas de problème, comme mentionné ci-dessus
Déplacez ce que vous voulez faire (programme) que vous avez écrit rapidement
Tracons l'opération. Je suis sûr que vous verrez ce qui manque.
Il n'y a pas de problème ici.
Montons, descendons, gauche et droite à partir d'ici.
À ce moment-là, compte tenu des restrictions susmentionnées, que devons-nous faire? .. ..
Essayons de monter, descendre, gauche et droite dans la case suivante.
Oh!? Je me suis séparé en deux.
Il est devenu nécessaire d'effectuer des traitements qui se déplacent dans toutes les directions aux coordonnées de [0,1] et [2,1].
Est-il possible de gérer la branche en tamponnant et en traitant chaque cas?
Cette fois, nous utiliserons la file d'attente. Il y a une raison pour cela.
Dans le précédent Regardons la somme partielle, si un point de branchement est créé,
J'ai choisi l'un des chemins et suis allé jusqu'à l'impasse (recherche prioritaire en profondeur).
Mais en jeûnant et en jeûnant les coordonnées du point de branchement sous forme de file d'attente,
Vous pouvez traiter les deux coordonnées du point de branchement, puis traiter la couche inférieure suivante, non?
Comme indiqué ci-dessous, l'image est rouge => bleu => vert et chaque couche est traitée puis traitée vers la couche inférieure.
Il semble que cela s'appelle ** recherche de priorité de largeur **.
Inversement, si vous changez la file d'attente en pile, ce sera une recherche prioritaire en profondeur.
Si c'est difficile à comprendre ou si c'est faux, veuillez commenter m (_ _) m
Maintenant, disons que vous avez la chance d'atteindre l'objectif.
Est-ce que c'est comme ça à ce moment-là?
** * Parce qu'il est gênant, seul l'itinéraire le plus court est peint en rouge. En réalité, les branches sont répétées, donc les carrés sur la route (bleu clair) doivent devenir rouges m (_ _) m **
Regardez le cadre vert dans la figure en haut à gauche. Tant que vous arrivez juste avant le but, il est naturel que vous deviez aller vers la droite, mais le fait est ** Cela signifie que la longueur des données mises en mémoire tampon dans la file d'attente ne sera jamais 0, même juste avant l'objectif **. À partir de ce qui précède, le processus de décision de la direction du voyage et de la procédure est répété avec l'instruction while, Il suffit de casser lorsque vous atteignez une certaine coordonnée.
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 = []#Coordonnées du tampon
buff.append([sx, sy])#ajouter des coordonnées de départ
distance[sx][sy]=0#Réécrire Aucun dans les coordonnées de début à 0
while len(buff):# len(buff) ==Boucle jusqu'à 0
x,y = buff.pop(0)#Mettez à jour votre position actuelle
if x == gx and y == gy:#pause lorsque vous atteignez l'objectif
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])#Buffer les coordonnées susceptibles d'avancer
distance[nx][ny] = distance[x][y] + 1
#Afficher le résultat final du mémo
print_maze(distance)
#Enfin renvoyer le mémo du point de but
return distance[gx][gy]
Résultat d'exécution.py
#Résultat mémo
None0NoneNoneNoneNoneNoneNone13None
212345None1312None
3None3NoneNone6NoneNone11None
4None4567891011
NoneNone5NoneNone8NoneNoneNoneNone
8767None9101112None
9NoneNoneNoneNoneNoneNoneNone13None
10111213None1716151415
11NoneNoneNoneNone18NoneNoneNone16
12131415None19202122None
#Distance au but
22
Je suis désolé, c'est difficile à comprendre, alors je vais le dessiner.
Le programme peut faire cela (..) φ memo memo
J'ai appris ('◇') ゞ
Recommended Posts