grid размером m × n: 0 — свободная клетка, 1 — стена. За один шаг можно перейти в соседнюю клетку вверх, вниз, влево или вправо.
У вас есть charges зарядов: один заряд позволяет пройти сквозь одну клетку-стену (разрушить её).
Найдите наименьшее число шагов от левой верхней клетки (0, 0) до правой нижней (m - 1, n - 1), если разрушить можно не больше charges стен. Если дойти нельзя, верните -1.grid=[[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]], charges=1 → 7
Без пролома пришлось бы петлять змейкой — 13 шагов. Ломаем стену (1, 0) и идём прямо вниз по левому краю, а потом вправо по нижнему ряду: 4 + 3 = 7 шагов.
grid=[[0, 1, 1], [1, 1, 1], [1, 1, 0]], charges=1 → -1
Любой путь из угла в угол проходит минимум через три стены, а заряд один.
grid=[[0, 0, 0], [0, 0, 0]], charges=2 → 3
Стен нет: три шага до правого нижнего угла.
grid=[[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]], charges=1
7
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 73 теста на сервере, включая скрытые.