Лабиринт с максимумом силы
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Матрицы и сетки
Дана прямоугольная таблица grid: -1 обозначает опасную клетку, в которую входить нельзя, положительное число — безопасную клетку с таким количеством силы. Из клетки можно сделать шаг вверх, вниз, влево или вправо. Вы стоите в клетке start и должны дойти до клетки finish (обе заданы как [строка, столбец], обе безопасны и различны), сделав как можно меньше шагов.
Сила клетки собирается один раз, когда вы в неё попадаете, включая стартовую и финишную клетки. Среди всех кратчайших путей выберите тот, на котором собрано больше всего силы, и верните эту сумму. Если дойти до finish нельзя, верните -1.
Пример: [[2, -1, 5], [3, -1, 6]], [0, 2], [1, 0] → -1 (стена из опасных клеток разделяет таблицу). Для [[3, 1, 1], [1, 1, 1], [1, 1, 8]], [0, 0], [2, 2] ответ 14: кратчайший путь делает 4 шага, а лучший из них собирает 3 + 1 + 1 + 1 + 8.
Источник: Coding Competitions Archive, kickstart/2013/round_b/dragon_maze · © Google LLC · Apache-2.0 · условие переведено и дополнено