deinier's blog

Do you have a different approach to this problem?
By deinier, 10 years ago, In English

Hi community!

I was requested to solve this problem few months ago in an onsite interview and I would like to know the best approach to solve it.

Problem statement:

You have a n * m grid with B (building), # (wall) and . (empty) and we want to know the coordinates i,j of a empty cell where the sum of the distances from all the buildings B to this cell is minimized. In each step you can move up, down, left and right. Each empty cell i,j is reachable for each building B.

My approach:

dist[i][j] -> sum of the distances from cell i,j to all buildings. (if we have B1 and B2 then dist[i][j] = distB1ij + distB2ij)

For each cell with a building B, apply BFS and increment dist[i][j] for all positions i, j reachable from B with the min distance from B to i, j in the grid.

Answer: min(dist[i][j]) where grid[i][j] is an empty cell.

Complexity:

O(n * m * (|V| + |E|)) where |V| is vertex amount (n * m) and |E| is edge amount (n * m).

at the end, I think my approach is O((n2)(m2))

My bad: I did not ask for any constraints. (Maybe I was a bit nervous that day)

Do you have another approach to this problem?

Am I wrong with this approach?

Thanks in advance.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

EDIT: I hand't understood the problem statement correctly. Sorry!

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    but if you only consider a empty cell only one time (the closest building to this cell will mark it as visited) then how do you know the sum of the distances to this cell from the rest of the buildings?

    Thanks for you help!

    EDIT: Oh, I did not see your update.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Edit: Sorry, I hadn't seen the walls.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You might want to start n(B) simultaneous BFS'es from each B, keep track of cells visited by each of them, and for each reachable cell keep the sum of BFS'es which hit it already. Once a cell with n(hits)=n(B) is found you break the search. Time complexity would be n(B) * max_distance_from_best_cell_to_furthest_B; still O(N*N) = O(n*n*m*m) (same as establishing distance between each two cells in the grid), but you break earlier.

→ Reply