This is a DFS solution, pretty straightforward but with a few caveats that took me a while to Iron out.

Some of the things that got me stuck:

- originally stopped after the first overlap, found that it doesn't guarantee that the first overlap of all buildings is optimal
- originally returned -1 after first building ran out of nodes, but that breaks if a building is located near the middle with other buildings on the edges.
- then changed it to keep going until all the buildings ran out of nodes, this caused time limit exceeded errors, the fix was to only run up to twice as long as the first building that stopped since in the worst case, there's a building in the middle with two buildings equidistance on opposite sides.

Here is the code:

```
def shortest_distance(grid)
@test= false
buildings=[]
@grid = grid
@n = @grid.length
@m = @grid[0].length if @grid[0]
(0...@n).each do |i|
(0...@m).each do |j|
buildings << [i,j] if @grid[i][j] == 1
end
end
@building_count = buildings.count
seen, queue = [], []
distances, counts, completed = {}, {}, {}
count = 0
shortest, first_finish = nil, nil
loop do
count += 1
break if (first_finish && (count > first_finish * 2))
buildings.each_with_index do |b, i|
next if completed[i]
seen[i] ||= {b.to_s => true}
queue[i] ||= [b]
new_queue = []
queue[i].each do |node|
new_queue += calc_neighbors(node[0], node[1], seen[i])
end
if new_queue.length == 0
completed[i] = true
first_finish ||= count
next
end
new_queue.each do |node|
counts[node.to_s] ||= 0
counts[node.to_s] += 1
distances[node.to_s] ||= 0
distances[node.to_s] += count
if counts[node.to_s] == @building_count
shortest ||= distances[node.to_s]
shortest = [shortest, distances[node.to_s]].min
end
end
queue[i] = new_queue
end
break if completed.count == @building_count
end
print_seen(seen, counts, distances) if @test
return shortest || -1
end
def print_seen(seen_set, counts, distances)
seen_set.each_with_index do |seen, index|
puts "printing seen set for #{index}"
(0...@n).each do |i|
row = ""
(0...@m).each do |j|
row += "= " && next if @grid[i][j] != 0
row += ". " && next if !seen[[i,j].to_s]
row += "X " && next if counts[[i,j].to_s] != @building_count
num = distances[[i,j].to_s].to_s
num += " "*(4 - num.length)
row += num
end
puts row
end
end
end
def calc_neighbors(i, j, seen)
options = [[i-1,j], [i,j-1], [i+1,j], [i,j+1]]
set = []
options.each do |p|
next if !valid?(p[0], p[1]) || seen[p.to_s]
set << p
seen[p.to_s] = true
end
return set
end
def valid?(i, j)
i >= 0 && j >= 0 && i < @n && j < @m && @grid[i][j] == 0
end
```