printРабочее место участника

printЗадачи

117. Назад из Клондайка

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (3)

Числовой лабиринт представляет собой квадрат размером `N`x`N` клеток, заполненный целыми числами в диапазоне от 1 до 9. Число в клетке означает, на сколько клеток нужно пройти по прямой за день из этой клетки в любом из восьми направлений по горизонтали, вертикали или диагонали. За пределы квадрата выходить нельзя. Из Клондайка в левом верхнем углу квадрата нужно попасть на опушку леса – на любую клетку нижнего или правого края квадрата.
Ввод
Во входном файле в первой строке находится целое число `N\ (2≤N≤30)`, далее следует `N` строк по `N` целых чисел в строке через один пробел.
Вывод
В выходной файл вывести минимальное число дней для прохождения лабиринта. Если выйти из лабиринта невозможно, то вывести число 0.

Пример ввода

4
1 4 5 1
8 1 3 3
3 9 6 4
1 7 2 1

Пример вывода

3
по диагонали вниз-вправо, затем вниз-влево, затем вправо
loading