Find the nearest building which has bike | Find nearest specific vertex from source in a graph.
Objective: Given a matrix (NxN) which represents the buildings in community. You are in a building and you need a bike to travel. There are few buildings in community which has bikes which you can take for your ride. Write an algorithm to find the nearest building which has bike and distance from your building.
- All buildings are at equal distance from its neighbor’s.
- Building’s e matrix is represented as 0 or 1. If bike is present in that building then 1 else 0.
Approach: Breadth – First Search
- Check if source building itself has a bike if yes then return source building with distance 0 else proceed.
- Add the source to the Queue.
- While queue is not empty
- Extract building from Queue.
- Visit all the neighbors (left, right, up and down, if possible) and increment the distance by 1. If any of the neighbors has bike return distance, else add them to the Queue.
Source building No: 0,3 Nearest building where bike is available is: 3,4 at distance: 4