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

Задачей является найти самый короткий путь для робота с использованием телепорта из клетки (1, 1) в клетку (N, M), при условии, что робот может двигаться только вправо или вниз и может использовать телепорт только один раз. Каждая клетка поля содержит положительное целое число.

1. Создадим двумерный массив dp размером N × M, где dp[i][j] будет содержать длину самого короткого пути от клетки (1, 1) до клетки (i, j).
2. Инициализируем dp[1][1] значением поля (1, 1).
3. Для каждой клетки (i, j) в поле, начиная с (1, 1) и двигаясь по строкам, затем по столбцам:
– Если i > 1 (не находится в первой строке), вычислим dp[i][j] = min(dp[i][j], dp[i-1][j] + поле[i][j]).
– Если j > 1 (не находится в первом столбце), вычислим dp[i][j] = min(dp[i][j], dp[i][j-1] + поле[i][j]).
– Если клетка (i, j) является телепортом, вычислим dp[i][j] = min(dp[i][j], dp[i-1][j-1] + поле[i][j]).
4. В результате dp[N][M] будет содержать длину самого короткого пути от клетки (1, 1) до клетки (N, M) с использованием телепорта.

Объяснение:
Мы идем от клетки (1, 1) до клетки (N, M) по строкам и столбцам. На каждом шаге мы выбираем наименьшее значение пути: либо из клетки сверху (i-1, j), либо из клетки слева (i, j-1), либо через телепорт из клетки (i-1, j-1). После прохода по всем клеткам мы получаем минимально возможную длину пути до клетки (N, M) с использованием телепорта.