Робот находится в левом верхнем углу прямоугольника 7×15. Ему надо покрасить правую верхнюю и левую нижнюю клетки прямоугольника. Остановиться он должен в правой нижней клетке.
Цель понятна: начать в левом верхнем углу прямоугольника 7×15, покрасить правую верхнюю клетку (1,15) и левую нижнюю клетку (7,1), и остановиться в правой нижней клетке (7,15).
1) Координаты клеток
- Начальная клетка: (1, 1)
- Правой верхней клетки: (1, 15)
- Левой нижней клетки: (7, 1)
- Правой нижней клетки: (7, 15)
2) Поиск оптимального пути
Чтобы минимизировать общее число ходов, рассмотрим два варианта порядка посещения требуемых клеток:
- Вариант A: Start → правый верхний (1,15) → левый нижний (7,1) → конец (7,15)
- Вариант B: Start → левый нижний (7,1) → правый верхний (1,15) → конец (7,15)
Посчитаем манхэттенские расстояния:
- d(Start, A) = d((1,1),(1,15)) = 14
- d(Start, B) = d((1,1),(7,1)) = 6
- d(A, B) = d((1,15),(7,1)) = 6 + 14 = 20
- d(B, End) = d((7,1),(7,15)) = 14
- d(A, End) = d((1,15),(7,15)) = 6
Суммарные расстояния для двух вариантов:
- Вариант A: 14 + 20 + 14 = 48
- Вариант B: 6 + 20 + 6 = 32
Оптимальный вариант: Start → B → A → End (то есть сначала левый нижний, затем правый верхний, затем правый нижний).
3) Конкретная последовательность движений
Стандартная сетка влияет так:
- Шаги вниз 6 разFrom (1,1) до (7,1): D×6 — достигаем левый нижний (7,1), который нужно покрасить.
- Шаги вверх 6 разFrom (7,1) до (1,1): U×6 — возвращаемся к начальной клетке (1,1). Это не требуется красить, но нужно для достижения (1,15) минимальным путём.
- Шаги вправо 14 разFrom (1,1) до (1,15): R×14 — достигаем правый верхний (1,15) и окрасим его.
- Шаги вниз 6 разFrom (1,15) до (7,15): D×6 — достигаем правой нижней (7,15) и останавливаемся.
Итого: D×6, U×6, R×14, D×6.
Общее число ходов: 6 + 6 + 14 + 6 = 32 ходa.
Ходы окрашивают:
- при достижении (7,1) окрашиваем левую нижнюю клетку;
- при достижении (1,15) окрашиваем правую верхнюю клетку;
- финальная остановка в (7,15) — правая нижняя клетка.
Если хотите, можно дополнительно привести альтернативный маршрут той же минимальной длины, но с другим обходом координат; однако данный вариант уже минимален по суммарному числу ходов.
