Разбор задач. Спецификация ввода-вывода. Множественное тестирование

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

  1. Написать три вида генераторов входных данных для задачи «лабиринт»:

    • «Простой» (случайная установка стен в пустом лабиринте)
      • Подобрать такую долю стен, чтобы в половине случаев лабиринт был проходим, а в половине — нет (предположительно 66%)
    • Случайный с «комнатами и колоннами». Лабиринт заполняется по схеме: · — всегда свободное место («комната»), # — всегда непроходимое место («колонна»), × — место, которое может быть проходимым, а может и нет («стена»):

      •     ·×·×·×·
            ×#×#×#×
            ·×·×·×·
            ×#×#×#×
            ·×·×·×·
    • С комнатми и колоннами по следующему алгоритму
      1. Заполняем всё камнями (тем самым помечаем комнаты «неизведанными»), кроме комнаты-входа. Помещаем комнату-вход в план разведки (список комнат, требующих разведки их соседей).
      2. Цикл до тех пор, пока план разведки не пуст.
        1. Выбираем последнюю комнату в плане разведки («исследуемую»)
        2. Если у неё нет неизведанных соседей, выбрасываем эту комнату из плана разведки и переходим к новому витку цикла
        3. Случайно выбираем одного из неизведанных соседей исследуемой комнаты («новую»)
        4. Заполняем нулями (проходами) новую комнату и стену между ней и исследуемой
    • Как изменится внешний вид лабиринта, если в п. 1.1 вместо последней выбирать случайную комнату из плана разведки?

    • Для того, чтобы сгенерировать непроходимый лабиринт, достаточно в п. 0. добавить в план разведки и вход, и выход! Почему? Реализовать генератор непроходимого или проходимого лабиринта (в зависимости от случайности или по запросу).

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


CategoryClass CategoryVmsh

LecturesVMSH/2011-12-14 (last edited 2011-12-31 11:51:24 by Ray)