Разбор задач. Спецификация ввода-вывода. Множественное тестирование
os.system(): циклический запуск программ-генераторов входных данных и решателей
- Спецификация ввода и вывода в олимпиадных задачах
Домашнее задание
Написать три вида генераторов входных данных для задачи «лабиринт»:
- «Простой» (случайная установка стен в пустом лабиринте)
- Подобрать такую долю стен, чтобы в половине случаев лабиринт был проходим, а в половине — нет (предположительно 66%)
Случайный с «комнатами и колоннами». Лабиринт заполняется по схеме: · — всегда свободное место («комната»), # — всегда непроходимое место («колонна»), × — место, которое может быть проходимым, а может и нет («стена»):
·×·×·×· ×#×#×#× ·×·×·×· ×#×#×#× ·×·×·×·
- С комнатми и колоннами по следующему алгоритму
Заполняем всё "#" (тем самым помечаем комнаты «неизведанными», а стены «непрорубленными»), кроме комнаты-входа. Помещаем комнату-вход в план разведки (список комнат, требующих разведки их соседей).
- Цикл до тех пор, пока план разведки не пуст.
- Выбираем последнюю комнату в плане разведки («исследуемую»)
- Если у неё нет неизведанных соседей, выбрасываем эту комнату из плана разведки и переходим к новому витку цикла
- Случайно выбираем одного из неизведанных соседей исследуемой комнаты («новую»)
Заполняем "." (проходами) новую комнату и стену между ней и исследуемой
- Добавляем этого соседа в план разведки.
Как изменится внешний вид лабиринта, если в п. 1.1 вместо последней выбирать случайную комнату из плана разведки?
Для того, чтобы сгенерировать непроходимый лабиринт, достаточно в п. 0. добавить в план разведки и вход, и выход! Почему? Реализовать генератор непроходимого или проходимого лабиринта (в зависимости от случайности или по запросу).
- «Простой» (случайная установка стен в пустом лабиринте)
Условные обозначения
— тема по Linux 
— необязательная тема 
— теоретическое задание 
— тема для самостоятельного изучения