Bonjour,

J'ai un exo à réaliser en Python mais je suis un peu perdu.

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
labyrinth = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
             [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
             [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1],
             [1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
             [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
             [1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],
             [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1],
             [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
             [1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
             [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
             [1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
             [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
             [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
             [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
             [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
 
class Labyrinth:
 
    def __init__(self, labyrinth, begin, end):
        self.__labyrinth = labyrinth
        self.__begin = begin
        self.__end = end
        self.__solution = []
 
    def set_solution(self, solution):
        self.__solution = solution
 
    def __str__(self):
        r = ""
        for y, line in enumerate(labyrinth):
            r += "\n"
            for x, c in enumerate(line):
                if c == 1:
                    r += u"\u2588" + u"\u2588"
                elif (x, y) == self.__begin:
                    r += 'b '
                elif (x, y) == self.__end:
                    r += ' e'
                elif (x, y) in self.__solution:
                    r += '::'                    
                else:
                    r += '  '
        return r
 
    def find_solution(self):
        """
        This method must return the shortest solution of the labyrinth.
        It's represented as the list of all the coordinates of the path's cells
        """
        return [(0, 19), (1, 19), (1, 18), (1, 17), (2, 17), (3, 17), (3, 16), (3, 15), (4, 15), (5, 15), (6, 15), (7, 15), (7, 16), (7, 17), (7, 18), (7, 19), (8, 19), (9, 19), (10, 19), (11, 19), (12, 19), (13, 19), (14, 19), (15, 19), (16, 19), (17, 19), (18, 19), (19, 19), (19, 18), (19, 17), (18, 17), (17, 17), (16, 17), (15, 17), (15, 16), (15, 15), (15, 14), (15, 13), (16, 13), (17, 13), (17, 12), (17, 11), (17, 10), (17, 9), (17, 8), (17, 7), (17, 6), (17, 5), (17, 4), (17, 3), (17, 2), (17, 1), (18, 1), (19, 1), (20, 1)]
 
l = Labyrinth(labyrinth, (0, 19), (20, 1))
solution = l.find_solution()
 
l.set_solution(solution)
print(l)
Les 1 représentent les murs et les 0 les endroits où l'on peut passer.
Le but est de remplir la fonction find_solution qui renvoie la liste des coordonnées du plus court chemin pour résoudre le labyrinthe.
Je pense que la façon la plus simple est d'utiliser le BFS mais je ne vois pas comment l'implémenter.

Merci d'avance,