347. Find the nearest building which has bike | Find nearest specific vertex from source in a graph.

Objective: Given a matrix (NxN) representing the community's buildings. You are in a building and you need a bike to travel.  There are a few buildings in the community with bikes you can take for your ride. Write an algorithm to find the nearest building that has a bike and distance from your building.  

NOTE:

1. All buildings are at an equal distance from their neighbors.
2. The building’s e matrix is represented as 0 or 1. If the bike is present in that building then 1 else 0.

Example:

Approach:  Breadth-First Search

1. Check if the source building itself has a bike if yes then return the source building with distance 0 else proceed.
2. Add the source to the Queue.
3. While the 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 a bike return distance, else add them to the Queue.

Output:

distance: 4
building: [3,4]

Related Problems:

- Max Flow Problem – Introduction Hard
- Graph Implementation – Adjacency Matrix | Set 3 Beginner
- Prim’s - Minimum Spanning Tree (MST) |using Adjacency Matrix Hard
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue without decrease key in O(ElogV) Hard
- Dijkstra’s – Shortest Path Algorithm (SPT) - Adjacency Matrix - Java Implementation Hard