Как развернуть стрелы остриями вверх за минимальное количество ходов

Если в задаче под «ходом» понимается поворот одной конкретной стрелки на фиксированный угол (как в большинстве головоломок: нажал на стрелку — она повернулась), то минимальное число ходов считается очень просто: каждую стрелку выгоднее крутить отдельно и ровно столько раз, сколько нужно до “вверх”. Поскольку стрелки не мешают друг другу (одна стрелка за ход — одна стрелка повернулась), оптимальность получается автоматически.

1) Если за ход стрелка поворачивается на 90° только в одну сторону (обычно по часовой)

Тогда для каждой стрелки нужно ровно столько нажатий, сколько осталось до положения “вверх” при вращении по кругу.

Удобно закодировать направления числами:

• ↑ = 0

• → = 1

• ↓ = 2

• ← = 3

Если стрелка сейчас в состоянии s, то чтобы сделать её ↑, нужно:

То есть по-человечески:

• стоит ↑ → нужно 0 ходов

• стоит → → нужно 3 хода (→ → ↓ → ← → ↑)

• стоит ↓ → нужно 2 хода (↓ → ← → ↑)

• стоит ← → нужно 1 ход (← → ↑)

Минимум ходов для всей картинки = сумма по всем стрелкам этих значений k.

Почему это минимум

Потому что:

• один ход влияет только на одну стрелку;

• у каждой стрелки есть единственное минимальное число поворотов по часовой до ↑ (его нельзя сделать меньше, иначе стрелка просто не успеет попасть в ↑);

• складываем неизбежное по каждой стрелке — получаем неизбежное по всей задаче.

2) Если за ход можно крутить на 90° в любую сторону (влево/вправо)

Тогда для каждой стрелки выбирается более короткий путь до ↑: по часовой или против.

Опять же, если направления закодированы как 0–3 (↑→↓←), то минимум для одной стрелки:

По смыслу это даёт:

• ↑ → 0

• → → 1 (повернуть влево на 90°)

• ↓ → 2 (в любую сторону по 180°)

• ← → 1 (повернуть вправо на 90°)

И снова минимум по задаче = сумма k по всем стрелкам.

3) Практический алгоритм “в руках”

1. Обходишь стрелки по одной (в любом порядке).

2. Для каждой смотришь, куда она сейчас смотрит.

3. Доворачиваешь до ↑ минимальным количеством шагов по правилам из пункта 1 или 2.

4. Суммируешь — это и будет минимальное число ходов.

Короткая памятка (самый частый вариант: только по часовой)

• ↑: 0

• →: 3

• ↓: 2

• ←: 1

Складываешь эти числа для всех стрелок — получаешь минимальное количество ходов.