SPOJ in Gyumri

   Лабиринт представлен матрицей NxN из 0 и 1. Цифрой "1" помечены непроходимые комнаты, а цифрой "0" - проходимые. Перемещаться можно только в проходимые комнаты, и только в те из них, которые имеют общую сторону. Время перемещения между двумя комнатами равно единице. Также за все путешествие можно один раз воспользоваться прыжком. Прыжок позволяет за одну единицу времени переместиться сразу на 2 клетки. С помощью прыжка можно перепрыгнуть непроходимую клетку. Прыгнуть можно только по направлению движения – влево, вправо, вверх, вниз. Ваша задача – найти кратчайший по времени путь из левой комнаты клетки в правую нижнюю. Гарантируется, что путь всегда существует.

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

   N– размер лабиринта (1 ≤ N ≤ 100).

   A[1,1] A[1,2] … A[1, N]

   …

   A[N,1] A[N,2] … A[N,N]

   A[i,j] – описание комнат лабиринта.

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

   Ans – кратчайший по времени путь из левой верхней комнаты в правую нижнюю.

Пример.