Студент

Бурин Никита

Задача

Волновой алгоритм в лабиринте

Состояние

Открыто

Дедлайн

Назначено

30.09.2015, 10:12

Найти наикратчайший путь для выхода из лабиринта, либо указать, что пути нет.

Входные данные

Текстовый файл с закодированным лабиринтом. Обозначения: 0 - пусто, 1 - стена, 2 - герой, 3 - выход.

Пример:

1 1 1 1 1 1 1 1 1 1
1 2 0 1 0 0 0 0 0 1
1 0 0 1 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0 3
1 0 0 0 0 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

Задача

Найти наикратчайший путь от позиции героя до точки выхода из лабиринта используя волновой алгоритм.

Передачу имён файлов реализовать через аргументы командной строки.

Выходные данные

Файл аналогичный исходному, в котором символами * обозначен путь от позиции героя до точки выхода.

Например:

1 1 1 1 1 1 1 1 1 1
1 2 0 1 0 0 0 0 0 1
1 * * 1 0 0 1 0 0 1
1 0 * 1 0 0 1 * * 3
1 0 * * 0 0 1 * 0 1
1 0 0 * * * * * 0 1
1 1 1 1 1 1 1 1 1 1

Допускается также визуализация пути псевдографикой в консоли. Можно, также, реализовать анимацию "побега".

Тестирование

Необходимо реализовать набор тестов, проверяющих корректность и оптимальность найденного пути, а также проверяющих корректность работы в ситуациях когда выхода нет, герой "замурован", герой отсутствует, и т.п..

Функции ввода/вывода нужно тестировать с помощью std::stringstream.