Grafy w Pythonie – Labirynt
# Tak można zdefiniować graf (pierwsza linia jest nieco przesunieta..) maze_txt = '''█████ ████ █ █ █ █ ██████ █ █ █ ████ █████''' start = 44 end = 5 print(maze_txt) # a to troche większy labirynt maze_txt = '''██████████████ █████ █ █ █ █████ ███ ████████ █ █ █ █ █ █ █████ ██████████ █ █ █ █ █ ████████ ██ █ █ ██ █ █ █ █ █ █ █ █ ██████ ██ █ ██ █ █ █ █ █ █ █████████ ██████████''' start = 209 end = 14 print(maze_txt) # policz wysokosc i szerokosc grafu - maze_lines = maze_txt.split("\n") h=len(maze_lines) w=len(maze_lines[0]) print(h, w, h*w) # zbuduj jeden dlugi tekst, ktory zawiera w sobie tylko znaki grafu # po tym tekscie bedzie mozna przemieszczac sie korzystajac z indeksow # usuwam entery zeby text odpowiadal numeracji wezlow maze_txt = maze_txt.replace('\n','') # proces budowy struktury grafu graph = [ [] for i in range(len(maze_txt))] # tu odbywa sie przeksztalcenie graficznej reprezentacji labiryntu # do postaci grafu # wierzcholki to pola labiryntu - droga lub sciana # krawedz, to mozliwosc przejscia do innego pola for i in range(len(maze_txt)): # Jesli przez to pole prowadzi droga if maze_txt[i] == ' ': # dla kazdego wezla musze ustalic co jest po lewej/prawej/wyzej/w dol on_left = None if i % w == 0 else i-1 on_right = None if (i+1) % w == 0 else i+1 on_up = None if i < w else i-w on_down = None if i + w > h * w else i+w # sprawdzic czy jest to droga i jesli tak, to dodac info do definicji grafu if on_left and maze_txt[on_left] == ' ': graph[i].append(on_left) if on_right and maze_txt[on_right] == ' ': graph[i].append(on_right) if on_up and maze_txt[on_up] == ' ': graph[i].append(on_up) if on_down and maze_txt[on_down] == ' ': graph[i].append(on_down) # funkcja do wyszukiwania najkrótszej drogi def is_path_between(V, source, dest): list_to_check = [[source]] list_visited = [] while list_to_check: current_path = list_to_check.pop(0) current_node = current_path[-1] if current_node == dest: return current_path else: if current_node not in list_visited: list_visited.append(current_node) for n in V[current_node]: new_path = current_path.copy() new_path.append(n) list_to_check.append(new_path) return [] # find shortest path between start and end path = is_path_between(graph, start, end) # narysuj graf, oznaczając znalezioną ścieżkę znakiem * for i in range(h): line = '' for j in range(w): if (i*w+j) in path: line+='*' else: line+=maze_txt[i*w+j] print(line)