Shortest Distance from All Buildings (BFS)

To solve this, I would first clarify the input constraints, specifically the maximum grid size and whether we assume connectivity. My approach involves a reverse BFS strategy. Instead of starting from every empty land, which could be inefficient, I will iterate through each building marked as '1'. For every building, I'll perform a Breadth-First Search to calculate the shortest distance to all reachable empty lands '0', accumulating these distances in a global sum matrix. Crucially, I will also maintain a visit count matrix to ensure that any candidate empty land has been reached by all buildings; if a land cell hasn't been visited by every building, it cannot be a valid solution. After processing all buildings, I will scan the sum matrix to find the minimum value among cells where the visit count equals the total number of buildings. If no such cell exists, I return -1. This method ensures we only traverse the grid once per building rather than per empty land, optimizing performance significantly. For example, in a 3x3 grid with two buildings, we run two BFS passes. The first pass adds distances from Building A, the second from Building B. We then check which zero-cell has the lowest total sum and was visited twice. This aligns well with Meta's focus on scalable algorithms for large-scale data structures.