Dsa
Graphs Bfs
Medium
Shortest Path in a City
You are given a grid representing a city where each cell can be a road (1) or a building (0). You can only travel on roads. Given the starting position and the destination position, determine the shortest path from the start to the destination in terms of the number of roads traversed.
Input:
- The first line contains two integers, R (rows) and C (columns) of the grid.
- The next R lines contain C integers each (0 or 1).
- The last line contains the coordinates of the starting point and the destination (x1 y1 x2 y2).
Output:
- An integer representing the length of the shortest path, or -1 if the destination is unreachable.
Example:
Input:
3 3
1 1 0
1 0 1
1 1 1
0 0 2 2
Output:
4
Key concepts
graphsbfsshortest-pathcity
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now