This post is completed by 2 users

  • 0
 Add to List
Hard

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: