Дано клетчатое поле размера N × M . У клетки из строки i и столбца j координаты ( i , j ) . У этого поля есть две особенности: В каждой клетке поля записано целое положительное число Некоторые клетки поля являются телепортами Роботу нужно пройти из левой верхней клетки с координатами ( 1 , 1 ) до правой нижней c координатами ( N , M ) . При этом робот из текущей клетки может переходить на одну клетку вправо или на одну клетку вниз. Также у робота есть одна возможность телепорта. Это з

Одна из возможных стратегий решения данной задачи – использование динамического программирования.

Шаги решения:
1. Создаем двумерный массив dp размера N x M, где dp[i][j] будет хранить наибольшую сумму чисел на пути от клетки (1, 1) до клетки (i, j).
2. Инициализируем dp[0][0] равным значению клетки (1, 1) поля.
3. Для первой строки и первого столбца, dp[i][0] и dp[0][j] равны сумме значений всех клеток слева или сверху соответственно, так как робот может перемещаться только вниз или вправо.
4. Для остальных клеток (i, j), значение dp[i][j] будет равно максимуму из суммы текущей клетки и значения dp[i-1][j] (значение сверху) и dp[i][j-1] (значение слева), так как робот может перемещаться только вниз или вправо.
5. Если клетка (i, j) является телепортом, то вместо значения dp[i][j] используем максимум из dp[i][j] и суммы текущей клетки с значением dp[i-1][j] (значение сверху) и dp[i][j-1] (значение слева), так как робот может использовать телепорт один раз.
6. На выходе получаем значение dp[N-1][M-1], которое является наибольшей суммой значений на пути к последней клетке.

Временная сложность данного решения составляет O(N*M), так как для каждой клетки выполняется константное количество операций.