board из m строк и n столбцов, заполненное неотрицательными числами. Вы стоите в левой верхней клетке (0, 0) и хотите попасть в правую нижнюю (m - 1, n - 1).
Из клетки (i, j) со значением v = board[i][j] можно за один ход перепрыгнуть:
- вправо по той же строке в любую клетку (i, k), где j < k ≤ j + v;
- вниз по тому же столбцу в любую клетку (k, j), где i < k ≤ i + v.
Верните наименьшее число клеток, которые придётся посетить по пути, включая стартовую и конечную. Если добраться нельзя, верните -1.board=[[1, 3, 2], [0, 0, 0], [0, 0, 0]] → 4
Путь (0, 0) → (0, 1) → (0, 2) → (2, 2): из (0, 2) со значением 2 можно спуститься сразу на две строки. Всего 4 клетки, считая стартовую и конечную.
board=[[4, 0, 0, 0, 0]] → 2
Из стартовой клетки можно прыгнуть сразу в последнюю: посещены 2 клетки.
board=[[2, 0, 0], [0, 0, 0], [0, 0, 0]] → -1
Из старта достижимы только клетки со значением 0, дальше двигаться некуда.
m, nm · n ≤ 10⁵board[i][j] < m · nboard[m - 1][n - 1] = 0board=[[1, 3, 2], [0, 0, 0], [0, 0, 0]]
4
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.