Описание задачи
Найти путь из левого верхнего угла карты в правый нижний с максимальным суммарным
подъёмом. Движение только вправо (E) или вниз (S). Ограничение: не более k
подъёмов подряд.
Правила
- E (East) — движение вправо
- S (South) — движение вниз
- Подъём — переход на клетку с бо́льшим значением
- k = 0 — подъёмы запрещены
Формат входных данных
> Dimensions:
rows cols
> Map:
v11 v12 v13
v21 v22 v23
...
> Query:
? k
Примеры
Карта 3×3:
10 10 10
20 20 10
30 30 10
? 1
Max: 20
* S -> E -> S -> E
? 0
Max: 0
* E -> E -> S -> S
? 100
Max: 20
* E -> S -> S -> E
* S -> E -> S -> E
* S -> S -> E -> E
? a
Invalid input.
Ключевые моменты
- Рекурсия с состоянием: (x, y, consecutive_climbs)
- При спуске/ровном переходе счётчик обнуляется
- Мемоизация для оптимизации