Форум программистов, компьютерный форум CyberForum.ru

Рекурсивный обход роботом плоской фигуры - C++

Восстановить пароль Регистрация
 
Mr_JEW
0 / 0 / 0
Регистрация: 12.11.2010
Сообщений: 3
12.11.2010, 20:28     Рекурсивный обход роботом плоской фигуры #1
Всем доброго времени суток. Помогите, пожалуйста, в решении задачи на рекурсию.

Необходимо, чтобы пользователь нарисовал какую-либо фигуру, поставил в неё робота, и тот обошёл бы её полностью, побывав на каждой клетке фигуры только один раз.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Grey
Тутошний я
 Аватар для Grey
1435 / 619 / 23
Регистрация: 03.11.2009
Сообщений: 1,600
14.11.2010, 03:01     Рекурсивный обход роботом плоской фигуры #2
Не полностью подходит Покрасить лабиринт
Может есть алгоритм по лучше.
побывав на каждой клетке фигуры только один раз
А если будет коридор, с проходом в одну сторону?
А если 2 коридора?
Mr_JEW
0 / 0 / 0
Регистрация: 12.11.2010
Сообщений: 3
14.11.2010, 13:30  [ТС]     Рекурсивный обход роботом плоской фигуры #3
Grey: Учитывая возможные коридоры.
Grey
Тутошний я
 Аватар для Grey
1435 / 619 / 23
Регистрация: 03.11.2009
Сообщений: 1,600
14.11.2010, 17:59     Рекурсивный обход роботом плоской фигуры #4
Цитата Сообщение от Mr_JEW Посмотреть сообщение
Grey: Учитывая возможные коридоры.
Я таких алгоритмов не знаю.
Если есть коридор, робот должен в последнюю очередь туда подходить. А если 2 коридора, он остановится в 1-ом, так как там уже проходил.
И не обязательно коридор, в любой фигуре кроме квадрата и прямоугольника, есть тупиковые места(если по диагонали не ходить).
Mr_JEW
0 / 0 / 0
Регистрация: 12.11.2010
Сообщений: 3
14.11.2010, 18:14  [ТС]     Рекурсивный обход роботом плоской фигуры #5
Grey: Ну, а если 1 коридор?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
14.11.2010, 18:22     Рекурсивный обход роботом плоской фигуры #6
Смотреть надо в сторону поиска гамильтоновых циклов в графе, который представляет фигуру. Клетки - вершины.
Yandex
Объявления
14.11.2010, 18:22     Рекурсивный обход роботом плоской фигуры
Ответ Создать тему
Опции темы

Текущее время: 02:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru