Поиск кратчайших путей прохождения маршрута в лабиринте (между входом и выходами)

Предмет: Алгоритмы и структуры данных, Информатика (раздел "Поиск кратчайших путей в графах").

Задание: Поиск кратчайших путей прохождения маршрута в лабиринте (между входом и выходами).

Требования:

1. Реализовать на языке Python.
2. Создать интерактивный графический интерфейс.
3. Вывести общее количество маршрутов с их длиной.
4. Вывести маршрут наименьшей длины.
5. Добавить интерактивные элементы управления для просмотра маршрутов по очереди и перехода к определённому маршруту.
6. Обеспечить возможность изменения конфигурации лабиринта.

Объяснение: По сути, для данного задания вам потребуется реализовать алгоритм для нахождения кратчайшего пути в графе (представленном в виде лабиринта). Один из предложенных алгоритмов — **Алгоритм Ли** (волновой алгоритм) — на основе поиска в ширину вполне подходит для данной задачи.

Решение на Python:

1. Модель лабиринта. Лабиринт можно представить как двумерный массив (список списков), где:
   • `1` обозначают стены,
   • `0` обозначают проходы,
   • синяя клетка — вход,
   • красная клетка — выходы.
2. Выбор алгоритма: Используем **поиск в ширину (BFS)** для нахождения кратчайшего пути от входа до выхода (или выхода).
3. Код решения:

   
   from collections import deque
   # Модель лабиринта, где 1 — это стена, 0 — это свободный проход
   maze = [
       [1, 1, 1, 1, 1, 1, 1, 1],
       [1, 0, 0, 0, 0, 0, 0, 1],
       [1, 0, 1, 1, 1, 0, 0, 1],
       [1, 0, 1, 0, 1, 0, 1, 1],
       [1, 0, 1, 0, 1, 0, 0, 1],
       [1, 0, 0, 0, 0, 1, 0, 1],
       [1, 1, 1, 1, 1, 1, 1, 1]
   ]
   # Координаты начала (входа) 
   start_x, start_y = 1, 1
   # Координаты финиша (выхода) 
   end_x, end_y = 5, 6
   # Поиск путей (алгоритм BFS)
   def bfs(maze, start, goal):
       rows, cols = len(maze), len(maze[0])
       queue = deque([start])
       distances = [[-1] * cols for _ in range(rows)]
       distances[start[0]][start[1]] = 0
       directions = [(0,1), (1,0), (0,-1), (-1,0)] # Право, Вниз, Лево, Вверх
       while queue:
           x, y = queue.popleft()
           if (x, y) == goal: break
           for dx, dy in directions:
               nx, ny = x + dx, y + dy
               if 0