Module: BFS - Umgehung in der Breite


Problem

3 /6


Weglänge

Problem

In einem nicht ausgerichteten Diagramm ist es erforderlich, die Länge des kürzesten Pfads zwischen zwei Stützpunkten zu finden.
 
Eingabe: 
- die Zahl N ist in der ersten Zeile der Eingabe geschrieben - die Anzahl der Scheitelpunkte im Diagramm (\(1<=N<=100\));
- als nächstes wird eine Adjazenzmatrix aus einer neuen Zeile geschrieben (0 bedeutet, dass keine Kante vorhanden ist, 1 bedeutet, dass eine Kante vorhanden ist);
- Die letzte Zeile enthält die Zahlen der beiden Scheitelpunkte, den Anfangs- und den Endpunkt.
 
Ausgabe: Geben Sie die Länge des kürzesten Pfads aus. Wenn kein Pfad vorhanden ist, geben Sie eine Zahl -1 aus.

 

Beispiele
Eingabe Ausgabe
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3