l**g
发帖数: 133 | 1 N*N的格子中有k个点，代表桌子，并且有障碍物，求一点到达各个k点的距离最短。只
可以四个方向前进。
另外这种图论的算法LC和面筋上面很少，哪里有比较全的资料可以复习？ |
G****n
发帖数: 618 | 2 感觉是walls and gates的变形。要找一个到所有k点的总和最短的点，就求枚举每一个
点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。
【在 l**g 的大作中提到】
: N*N的格子中有k个点，代表桌子，并且有障碍物，求一点到达各个k点的距离最短。只
: 可以四个方向前进。
: 另外这种图论的算法LC和面筋上面很少，哪里有比较全的资料可以复习？
|
l**g
发帖数: 133 | 3 [在 Gallen (Gallen) 的大作中提到：]
:感觉是walls and gates的变形。要找一个到所有k点的总和最短的点，就求枚举每一
个点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。
还有没有其他的优化思路？除了prune以外。 |
r*******e
发帖数: 7583 | 4 从k个点出发BFS，记录k点到任意一点的距离，然后求和的最小值。不需要从每一个点
出发BFS。
【在 G****n 的大作中提到】
: 感觉是walls and gates的变形。要找一个到所有k点的总和最短的点，就求枚举每一个
: 点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。
|
g*********e
发帖数: 14401 | 5 从每个桌子bfs 把距离算出来，然后把距离加起来，找最小的距离和
【在 l**g 的大作中提到】
: N*N的格子中有k个点，代表桌子，并且有障碍物，求一点到达各个k点的距离最短。只
: 可以四个方向前进。
: 另外这种图论的算法LC和面筋上面很少，哪里有比较全的资料可以复习？
|
l**g
发帖数: 133 | 6 所以距离之和最小一定是在几个k点之中，那这个是为什么呢？ |
e***a
发帖数: 150 | 7 就是这个，没啥变形
【在 G****n 的大作中提到】
: 感觉是walls and gates的变形。要找一个到所有k点的总和最短的点，就求枚举每一个
: 点到这k个点的总和。最直接的方法就是以每一个点作为起点进行BFS。
|
w*******d
发帖数: 59 | |
a****x
发帖数: 93 | 9 只看第一步：
“从k个点到任意一点的最短距离”和“从任意一点到k个点的最短距离”有什么区别吗？
完全是一样的啊，没有任何优化
一个
【在 r*******e 的大作中提到】
: 从k个点出发BFS，记录k点到任意一点的距离，然后求和的最小值。不需要从每一个点
: 出发BFS。
|
l**g
发帖数: 133 | 10 哦，理解错了。所以一种类似dp的方法：
从第一个桌子出发，计算到各个点的距离，存在N*N里，然后从下一个桌子出发，更新
每个点算出来每个点到两个桌子的距离，依此类推直到k个桌子，找到距离里最小值就
可以
memory：N*N, 包括BFS开销
time: N*N*k, 每个桌子要遍历所有点 |
|
|
w******h
发帖数: 20 | 11 有个corner case是如果有一个桌子到不了某个点，那么这个点的距离不能用来更新结
果的最小值，面试的时候也碰到这题了，这个corner case没想到，面试官提示了半天
才想出来。google就要求一次啥都写对所有的corner case都考虑到嘛..错一点都不行.
.是gg要求略苛刻还是我太弱了...
【在 l**g 的大作中提到】
: 哦，理解错了。所以一种类似dp的方法：
: 从第一个桌子出发，计算到各个点的距离，存在N*N里，然后从下一个桌子出发，更新
: 每个点算出来每个点到两个桌子的距离，依此类推直到k个桌子，找到距离里最小值就
: 可以
: memory：N*N, 包括BFS开销
: time: N*N*k, 每个桌子要遍历所有点
|
a*******g
发帖数: 1221 | |
l**g
发帖数: 133 | |
s***c
发帖数: 639 | 14 这道是收费题，新一些的面筋现在大都是收费的了
【在 a*******g 的大作中提到】
: 这不就是这道题吗？
: https://leetcode.com/problems/shortest-distance-from-all-buildings/
: 大家得刷题啊。
|
i******t
发帖数: 22541 | 15 这个用最短路径计算不就完了dijkstra shortest path
作 k 次 不久完了？ |
l**g
发帖数: 133 | |
