j*********n
发帖数: 34 | 1 1.
Given multiple printers on a grid map, find the location to place papers
such that the sum of distance from the
paper to all printers is minimal; note that there are obstacles in the grid
map. What if there is no obstacles?
2
2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
问
如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
需要绕开，拿到以后要放回出发点，然后再取另一个
＊＊＊＊＊＊
＊ ＃ ＊
＊ ＊＊＊ ＊
＊ ＊
＊ ＊＊ ＊
＊ ＃ ＃＊
＊＊ ＊＊＊＊
如果没有障碍物，就是曼哈顿最短距离，http://stackoverflow.com/questions/10402087/algorithm-for-minimum-manhattan-distance，如果有障碍物，什么算法比较好？ 大牛请解惑 |
P*******L
发帖数: 2637 | 2 2 用 BFS？
grid
【在 j*********n 的大作中提到】
: 1.
: Given multiple printers on a grid map, find the location to place papers
: such that the sum of distance from the
: paper to all printers is minimal; note that there are obstacles in the grid
: map. What if there is no obstacles?
: 2
: 2d array ＊代表障碍物 ＃代表货物 空白就是正常的路
: 问
: 如何找到一个点为出发点 能实现总共取货路径最短？ 每次只能拿一个货物，遇到障碍
: 需要绕开，拿到以后要放回出发点，然后再取另一个
|
j*********n
发帖数: 34 | 3 1和2其实是一样的题，都有在有障碍物的情况下，求一点到其他已知点的最小距离。
BFS肯定是用BFS, 但BFS怎么做好呢？ 比如第2题，一种方法对所有 '#‘做BFS，另一
种方法是从所有空白格做BFS. 不过都不efficient， 有什么好办法吗？
【在 P*******L 的大作中提到】
: 2 用 BFS？
:
: grid
|
l****i
发帖数: 2772 | |
x******0
发帖数: 178 | 5 有障碍物，用BFS 算每个点到所有打印机/货物的距离和？这不是标准的brute force么
。。 |
