@aygumov
Дагестанец

Как найти длинный путь между двумя точками?

63119b8c325bf040571327.jpeg

Как искать самый длинный путь между ее головой и красной точкой?
  • Вопрос задан
  • 214 просмотров
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Зачем вам самый длинный путь? Вообще, эта задача очень сложная. Кратчайший путь можно найти обходом в щирину или глубину, быстро и просто. Самый длинный - только полным перебором. Возможно, его можно как-то соптимизировать используя особенности вашей конкретной задачи (вроде заполнения прямоугольника змейкой и конструтирование маршрута из таких шаблонов), но это тоже очень сложно.
Ответ написан
maaGames
@maaGames
Погроммирую программы
Самый длинный путь - эта задача нерешаема, т.к. в самом начале игры змейка будет просто кругами бегать ВЕЧНО, ведь нет запрета на посещение одной и той же клетки.
Но вы решаете совсем другую задачу.
У вас задача съесть точку и удлинить змею, но не уткнуться в себя самого.
Для этого задаёте список правил, которые, с большой долей вероятности, позволят эту точку избегать:
2. двигаться вдоль границ игрового поля
1. двигаться вдоль тела змейки
3. ВАЖНО! не создавать петли. т.е. приближаясь к хвосту/стенке нежелательно оставлять незаполненные области
4. избегать движения к точке
5... ещё что-нибудь, что сразу в голову не приходит
X. делать пункты 1-4 на несколько ходов вперёд. Допустим, на 50 щагов вперёд можно без проблем просчитываь. Если на 47 шаге скушали точку, при этом оставались пустые клетки, то отматываете назад и пробуете двигаться в другие стороны.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
@NIKROTOS
Начинающий программист.
Просто поворачивай дважды в крайних положениях и дойдёшь до конца(разворот на 180 на краю)
Ответ написан
Комментировать
LaRN
@LaRN
Senior Developer
В конкретно в этой задаче кажется, что самое длинное расстояние, это количество ячеек игрового поля в области, которая содержит красную точку. Т.е. это можно попробовать решить каким либо алгоритмом заливки области цветом.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы