Mobile coding works. A laptop is faster for long sessions.
Problem
Given an undirected graph with `n` vertices via its adjacency matrix, and
two vertices `s` and `t`, determine the **length of the shortest path** between
`s` and `t`, measured as the number of edges.
If `s == t`, the answer is `0`. If no path exists between `s`
and `t`, print `-1`.
Input:
The first line contains three natural numbers, `n`, `s` and `t`, separated by
spaces. The following `n` lines each contain `n` binary values: the adjacency
matrix.
- `1 <= n <= 50`
- `1 <= s, t <= n`
- use breadth-first search (BFS) implemented with an array
Output:
The program prints to standard output a single integer: the minimum path length from
`s` to `t`, or `-1` if the two vertices are not in the same
connected component.
Example:
Input:
6 1 6
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 1 0 0
0 1 1 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0
Output:
4
Stuck?
Use the Get Hint button in the action bar to reveal a guided hint.
💬 Discussion
Loading...💬
No comments yet. Be the first to start the discussion!
💻 No output yet.
Click Run in the editor to execute your code with the custom input.
Solve it your way first
Community solutions unlock after you submit a passing solution. Don't peek.
Ready to solve this challenge?
Create a free account to write code, submit solutions, and track your progress.
⌨️ Keyboard Shortcuts
Code Editor
Run Code
Ctrl
Enter
Submit Code
Ctrl
Shift
Enter
Format Code
Shift
Alt
F
Toggle Comment
Ctrl
/
Undo
Ctrl
Z
Redo
Ctrl
Y
Navigation
Global Search
/
Show Shortcuts
?
Close Modal
Esc