eolymp
bolt
Try our new interface for solving problems
Problems

Breadth First Search

Breadth First Search

Given an undirected graph. Find the shortest distance between two specified vertices. \InputFile The first line contains three positive integers $n, s$ and $f\:(1 \le s, f \le n \le 100)$ --- the number of vertices in the graph and the numbers of the initial and final vertices. Then, in $n$ lines, the adjacency matrix of the graph is given. If the value in the $j$-th element of the $i$-th row is $1$, then there is a directed edge from vertex $i$ to vertex $j$ in the graph. \OutputFile Print the minimum distance from the initial vertex to the final one. If the path does not exist, then print $0$. \includegraphics{https://static.e-olymp.com/content/37/37e209e3bcdf6dd58dcff5aa802392972e835fd4.gif}
Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4 3
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
Output example #1
2
Source SСS - 2011 Sevastopol 08/08/2011 d.2 1st League