Алгоритм Флойда

• Решение задачи «одномерный лабиринт» алгоритмом Флойда
• Условия применимости алгоритма Флойда
• Решение задачи о проходмости лабиринта
  • Восстановление кратчайшего пути
• Решение задачи о городах (минимальная стоимость проезда с пересадками)

Домашнее задание

1. Прочитать про Алгоритм Флойда-Уоршалла на e-maxx.ru

2. Лабиринт. Лабиринт задан списком строк следующего вида ("." — проходимая клетка, "#" — непроходимая)

       .#...........
       .#####.#####.
       ...#...#...#.
       ##.#.###.###.
       ...#.#.......
       .###.#.######
       .#...#...#...
       .###.###.#.##
       .....#.#.#...
       ######.#.###.
       .#.....#.....
       .#.#.#######.
       ...#.........

   Написать программу, которая:
   • умеет выводить лабиринт в красивом виде
   • Проверяет, можно ли добраться из клетки (0,0) в клетку (M-1,N-1)
   • … + вычисляет длину минимального пути
   • … + выводит маршрут
3. Написать генератор входных данных (для ввода со стандартного ввода можно впоследствии использовать конструкции вида python generator.py | python solver.py в командной строке или eval(строка-сгенерированная-генератором) в коде решения)
   • Просто какого-то лабиринта
   • Лабиринта, который с достаточной вероятностью может быть проходим или непроходим
   • Проходимого или непроходимого лабиринта по требованию
   • Лабиринта с ветвящимися путями
   • «Красивого» лабиринта как на примере

     • Намеренно непонятный (решайте задачу сами ) генератор лабиринта в виде "...#...#"

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh