eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сетка

Сетка

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Вы находитесь в верхнем левом углу сетки размера m * n, в каждой ячейке сетки находится одна цифра. Из ячейки с цифрой k на ней можно совершить прыжок в точности на k клеток в любом из четырех направлений (вертикальном или горизонтальном). Какое минимальное количество ходов требуется для перехода из верхнего левого угла в правый нижний?

Входные данные

Первая строка содержит два натуральных числа m и n (1m, n500). Гарантируется, что хотя бы одно из чисел m или n больше 1. Каждая из следующих m строк содержит n цифр, описывающих сетку m * n. Каждая цифра лежит в пределах от 0 до 9.

Выходные данные

Выведите минимальное количество ходов, необходимых для перехода из верхнего левого угла в нижний правый. Если невозможно достичь нижнего правого угла, выведите IMPOSSIBLE.

Пример

Входные данные #1
2 2
11
11
Выходные данные #1
2
Входные данные #2
2 2
22
22
Выходные данные #2
IMPOSSIBLE
Источник 2015 ACM North America - Pacific Northwest, Дивизион 2, Задача O