##master-page:VMSHClassTemplate
##master-date:Unknown-Date
#format wiki
#language ru
= Алгоритм Флойда =

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

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

  1. {i} Прочитать [[http://e-maxx.ru/algo/floyd_warshall_algorithm|про Алгоритм Флойда-Уоршалла на e-maxx.ru]]
  1. Лабиринт. Лабиринт задан списком строк следующего вида ("." — проходимая клетка, "#" — непроходимая)
  {{{
    .#...........
    .#####.#####.
    ...#...#...#.
    ##.#.###.###.
    ...#.#.......
    .###.#.######
    .#...#...#...
    .###.###.#.##
    .....#.#.#...
    ######.#.###.
    .#.....#.....
    .#.#.#######.
    ...#.........
  }}}
  Написать программу, которая:
   *      умеет выводить лабиринт в красивом виде
   *     Проверяет, можно ли добраться из клетки (0,0) в клетку (M-1,N-1)
   *     … + вычисляет длину минимального пути
   *     … + выводит маршрут 
  1. Написать генератор входных данных (для ввода со стандартного ввода можно впоследствии использовать конструкции вида python generator.py | python solver.py в командной строке или eval(строка-сгенерированная-генератором) в коде решения)
   *     Просто какого-то лабиринта
   *     Лабиринта, который с достаточной вероятностью может быть проходим или непроходим
   *     Проходимого или непроходимого лабиринта по требованию
   *     Лабиринта с ветвящимися путями
   *     «Красивого» лабиринта как на примере
    * Намеренно непонятный (решайте задачу сами :) ) [[attachment:../2013-01-18/labpurc.py|генератор лабиринта в виде "...#...#"]]

==== Условные обозначения ====
 . {o} — тема по Linux
 . <!> ­— тема повышенной сложности
 . {i} — теоретическое задание
 . {*} — тема для самостоятельного изучения

----
CategoryClass CategoryVmsh