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