Leetcode Problem 317. Shortest Distance from All Buildings

317. Shortest Distance from All Buildings

Leetcode Solutions

BFS from Houses to Empty Land (Optimized)

  1. Initialize total matrix with the same dimensions as grid to store the sum of distances from houses to empty lands.
  2. Set emptyLandValue to 0 and minDist to INT_MAX.
  3. For each cell in grid, if it is a house (value equals 1), start a BFS:
    • Use a queue to perform BFS.
    • For each cell visited, if its value equals emptyLandValue, update the total matrix with the distance and decrement the cell's value by 1.
  4. After each BFS traversal, decrement emptyLandValue by 1.
  5. After all BFS traversals, iterate over the total matrix to find the minimum distance for cells with housesReached equal to the total number of houses.
  6. If minDist is still INT_MAX, return -1. Otherwise, return minDist.
UML Thumbnail

BFS from Empty Land to All Houses

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...