Woodstock Blog

a tech blog for general algorithmic interview questions

[Google] Barrier, Goods Van and Distance



2d array *代表障碍物 #代表货物 空白就是正常的路

问如何找到一个点为出发点 能实现总共取货路径最短? 每次只能拿一个货物,遇到障碍需要绕开,拿到以后要放回出发点,然后再取另一个.

*  #           *
*  ***  *   *
*              *
*     **   * *
*  #    # # ***


This looks like a very difficult question, especially during a phone interview.

The 10th floor gives the best solution:

BFS from every box. in each box, a non-blocking cell (include box position, but exclude hazard position) will have a weight value, stand for the distance to the box.

after bfs from all the boxes, each cell will have k weight, k is the number of boxes. sum all the weight in each cell, and find the cell with smallest sum of weight.

One problem of this solution may lead to a cell of a box. We can then sort the cell by sum of weight and find the first position that is not a box.

complexity O(k*n2)

Suggested at this post, we can also use A* search (with heuristic function) to solve.


not written