ВУЗ:
Составители:
Рубрика:
# выход
? неизвестное состояние комнаты или стенки
Если существует несколько планов уровней, удовлетворяющих
условиям задачи , достаточно напечатать любой, если план
построить не удаётся, программа должна напечатать строку NO.
2. Алгоритм решения.
Для построения плана необходимо соотнести донесения всех
обезьянок так, чтобы они не противоречили друг другу .
Используется бэк-трэкинг, расшифровывающий маршрут
очередной обезьянки , и если это приводит к конфликту , последний
маршрут отменяется, и производится попытка согласовать
маршрут этой обезьянки , предположив, что в начальный момент
она смотрела в другую сторону и т.д. Если все четыре начальных
направления обезьянки приводят к конфликтам , считается, что
план для этой обезьянки построить не удается, что вызовет
изменение начального направления предыдущей обезьянки и т. д .
до первой. Откат реализуется с помощью рекурсии, а состояния
плана хранятся в стеке .
Если при какой-либо комбинации начальных состояний всех
обезьянок план построен, он и является ответом . Если такой
комбинации нет, плана не существует.
3. Программная реализация.
Program Labirint; {Автор-Клинских А.А.}
const
MaxN=50;
MaxM=50;
type
TPoint=record
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
