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. 図1.PNG 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. 図2.PNG 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? 図4.PNG 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. 図5.PNG 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?

  1. Pas un mur
  2. Ne sautez pas hors des coordonnées définies
  3. 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. 図6.PNG 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? .. .. 図7.PNG Essayons de monter, descendre, gauche et droite dans la case suivante. 図8.PNG 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. 図11.PNG 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à? 図9.PNG ** * 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. 図10.PNG Le programme peut faire cela (..) φ memo memo J'ai appris ('◇') ゞ

Recommended Posts

Je me suis perdu dans le labyrinthe
Mémo que je suis resté coincé dans l'introduction de Mezzanine
J'ai participé au tour de qualification ISUCON10!
J'ai écrit la file d'attente en Python
J'ai écrit la pile en Python
J'ai eu un AttributeError en me moquant de la méthode ouverte en python
J'ai essayé de sauvegarder les données récupérées au format CSV!
Tri sélect écrit en C
Je ne peux pas obtenir l'élément dans Selenium!
J'ai écrit l'aile coulissante dans la création.
J'ai essayé de simuler "Birthday Paradox" avec Python
J'ai essayé la méthode des moindres carrés en Python
Je ne peux pas saisir de caractères dans la zone de texte! ?? !! ?? !! !! ??
J'ai essayé d'implémenter la fonction gamma inverse en python
[PyTorch] J'étais un peu perdu dans torch.max ()
J'ai vérifié le calendrier supprimé dans le calendrier de l'Avent Qiita 2016
J'ai essayé d'implémenter Human In The Loop - Partie ① Tableau de bord -
Je veux afficher la progression en Python!
J'ai eu la date du riz du pub de Kagawa et j'ai dessiné un graphique
Ce que j'ai fait quand je suis resté coincé dans le délai avec lambda python
django geodjango auquel j'ai fait référence quand je suis resté coincé dans le tutoriel (édition)
J'ai essayé de représenter graphiquement les packages installés en Python
Ce que je suis entré dans Python pour la première fois
Celui qui se perd souvent dans la dénomination des variables
Je veux écrire en Python! (3) Utiliser des simulacres
J'ai un sqlite3.OperationalError
J'ai installé InsecurePlatformWarning en python, j'ai donc installé des requêtes [sécurité]
J'ai compté les grains
[Note] Le module installé ne peut pas être appelé dans jupyter.
Ce que j'ai appris en participant aux qualifications ISUCON10
Je veux utiliser le jeu de données R avec python
Je ne peux pas utiliser la commande darknet dans Google Colaboratory!
J'avais des problèmes car la chaîne de caractères dans le PDF était étrange
J'ai participé à l'activité de traduction du document officiel Django
J'ai essayé l'algorithme de super résolution "PULSE" dans un environnement Windows
Ce que je suis resté coincé autour de l'interface graphique dans l'environnement python WSL
J'ai eu une erreur dans vim ou zsh dans la série Python 3.7
J'ai écrit le fonctionnement de base de Seaborn dans Jupyter Lab
J'ai essayé de résumer le code souvent utilisé dans Pandas
J'ai essayé d'illustrer le temps et le temps du langage C
J'ai essayé de programmer le test du chi carré en Python et Java.
Je l'ai écrit en langage Go pour comprendre le principe SOLID
J'ai essayé de résumer les commandes souvent utilisées en entreprise
J'ai essayé d'implémenter la fonction d'envoi de courrier en Python
Je n'arrive pas à me connecter à la page d'administration avec Django 3
J'ai écrit le fonctionnement de base de Numpy dans Jupyter Lab.
Je veux rendre le type de dictionnaire dans la liste unique
Je veux aligner les nombres valides dans le tableau Numpy
J'ai implémenté N-Queen dans différentes langues et mesuré la vitesse
J'ai écrit un script qui divise l'image en deux
Je ne voulais pas écrire la clé AWS dans le programme
J'ai eu une erreur lorsque j'ai essayé de traiter luigi en parallèle dans Windows, mais la solution
J'ai écrit python en japonais
J'ai examiné l'arborescence des appareils
Trouver des erreurs en Python
5 raisons pour lesquelles je suis entré dans Python
J'ai tweeté depuis le terminal!
J'ai essayé de toucher l'API Qiita
J'ai essayé la bibliothèque changefinder!