Имеется каретка, движущаяся по осям X и Y, и поле, разделенное на 24 квадрата вот так: 1 2 3 4 5 6 первый ряд, 7 8 9 10 11 12 второй ряд и т.д. Подскажите алгоритм оптимального перемещения каретки от квадрата 1 до квадрата 24.
-
2@Hermann Zheboldov, а чем определяется оптимальность? Минимальным пройденным расстоянием? Количеством поворотов каретки? Ещё чем-нибудь? Нужно ли посещать каждый квадрат или задача просто переместиться из 1 в 24? Каретка движется только параллельно осям X и Y?– fori1ton25 фев 2015 в 13:58
-
В принципе, задач по большому счету две: 1. Посетить каждый квадрат. 2.Посетить квадрат с такого-то по такой-то. Во второй задаче нужно к начальному квадрату переместиться по оптимальной траектории. Каретка движется только параллельно осям– Hermann Zheboldov25 фев 2015 в 14:04
-
@Hermann Zheboldov: Давайте-ка я повторю вопрос: что есть "оптимальная траектория"? Если кратчайшая, то ответ тривиален: идёте по горизонтали, пока не попадёте в нужный столбец, потом по вертикали до нужной клетки. Соответственно если нужно посетить каждый квадрат, идёте по строкам, меняя направление.– VladD25 фев 2015 в 14:16
-
Да, я неправ. Поясняю подробнее. На каретка стоит фотокамера, фотографирующая заданные квадраты. Как у меня работает сейчас. Если нужно отснять квадраты с 1 по 7, то каретка доезжает до квадрата 6, съезжает вниз и возвращается в квадрат 7. Все нормально. Но в случае, когда нужно отнять, например, с 1 по 11, то каретка все равно доползает до квадрата 7 и, двигаясь потом вправо, доснимает оставшиеся квадраты. А вот хотелось бы, чтобы камера, попав в квадрат 11 начала бы съемку и закончила бы в квадрате 7. Вот этот алгоритм я и не могу закодить.– Hermann Zheboldov25 фев 2015 в 14:56
Добавить комментарий
|
1 ответ
Вот этот алгоритм я и не могу закодить.
Примерно так, если я правильно понял проблему...
Для случая 1..n, например, CurPos=1 (текущий квадрат), ряды снизу вверх:
- Сначала идём всегда вправо, пока не упёрлись или не достигли n.
- Потом поднимаемся вверх на 1 и меняем направление.
- Ставим флаг, нужно ли нам будет продолжать движение по y в будущем, т.е. если СuPos>=n, то это последняя строка).
- Если CurPos<=n -> "сняли".
- Иначе просто продолжаем движение влево, пока не упёрлись.
- Повторяем с шага 2.