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

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

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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/Python/2016-02-19 (last edited 2016-02-21 01:33:40 by FrBrGeorge)