Задача E. Шарик в лабиринте ≡

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Юный программист Петя все свободное от написания программ и приема пищи время посвящает известной карманной игре "Шарик в лабиринте", суть которой заключается в том, чтобы провести шарик по пластмассовому лабиринту. Для этого лабиринт можно наклонять, отчего шарик начинает катиться по проходу с ускорением g = 9,811м / с2. Шарик катится строго по прямой параллельно сторонам лабиринта. На поворотах шарик мгновенно и полностью останавливается.

Лабиринт имеет размер N × N см и высоту 1 см и состоит из клеток — кубиков 1 × 1 × 1 см. Каждый такой кубик является либо проходом, либо стенкой. Ровно один из кубиков помечен как выход из лабиринта.

Требуется определить минимальное время, за которое шарик можно перекатить из левого верхнего угла лабиринта к выходу.

Примечание

Путь, пройденный равноускоренно движущимся из состояния покоя телом за время t, равен gt2 / 2.

Формат входного файла

В первой строке входного файла задано число N. В следующих N строках задано описание лабиринта. Каждая строка описания состоит из N цифр от 0 до 2, разделённых пробелами. Здесь 0 соответствует пустой клетке, 1 — стенке, 2 — выходу. При этом цифра 2 встречается во всем описании ровно один раз, а первая цифра первой строки не равна 1.

Формат выходного файла

В выходной файл нужно вывести минимальное время в секундах с точностью до трёх знаков после запятой или число -1, если перемещение шарика к выходу невозможно.

Ограничения

1 ≤ N ≤ 10.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
0 1 1
1 0 1
2 0 0
 
-1
2 
4
0 0 0 1
0 0 0 0
0 1 1 0
0 0 0 2
 
0.156
0.060s 0.008s 13