Описание
Отправленные решения

12. Длина кратчайшего пути

Не решаласьЛёгкая

Дан неориентированный граф. Найдите длину минимального пути между двумя вершинами.

Формат ввода

В первой строке записано целое число $N$ ($1 \leq N \leq 100$) – количество вершин в графе.

Далее записывается матрица смежности — $N$ строк, в каждой из которых содержится $N$ чисел 0 или 1, разделённых пробелом. Число 0 означает отсутствие ребра, а 1 — наличие ребра.

В последней строке задаются номера двух вершин — начальной и конечной.

Вершины нумеруются с единицы.

Формат вывода

Выведите длину кратчайшего пути — минимальное количество ребер, которые нужно пройти.

Если пути нет, нужно вывести -1.

Ограничения

Ограничение времени: 1 с
Ограничение памяти: 64 МБ

Пример 1

Ввод

10
0 1 0 0 0 0 0 0 0 0 
1 0 0 1 1 0 1 0 0 0 
0 0 0 0 1 0 0 0 1 0 
0 1 0 0 0 0 1 0 0 0 
0 1 1 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 1 
0 1 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 0 0 
0 0 0 0 1 1 0 0 0 0 
5 4

Вывод

Пример 2