y******s
发帖数: 92 | 1 input：char[][] matrix, Point[] robots
output: int
给一个矩阵，0代表可以通过，x 代表障碍物，不能通过，r代表机器人，求找出一点
使得所有机器人到该点的sum 最小
0 R 0 0 0
0 0 x R x
x 0 R 0 x.
0 0 0 0 0
最直接的思路就是从一个机器人开始做BFS，算出这个机器人到每一个点的最短距离，
然后把所有机器人到该点的距离相加，得到最短的那个点。但是这样复杂度就很大了，
大概要O(r*m*n)，r为机器人个数，m和n为矩阵长宽。
不知道还有什么更好的方法吗？ |
y******s
发帖数: 92 | |
f*********s
发帖数: 1881 | 3 感觉是求所有点到所有点的最短距离，可以用bellman ford法。
另外，这个图看起来有点像8皇后，也许可以考虑回溯
【在 y******s 的大作中提到】
: input：char[][] matrix, Point[] robots
: output: int
: 给一个矩阵，0代表可以通过，x 代表障碍物，不能通过，r代表机器人，求找出一点
: 使得所有机器人到该点的sum 最小
: 0 R 0 0 0
: 0 0 x R x
: x 0 R 0 x.
: 0 0 0 0 0
: 最直接的思路就是从一个机器人开始做BFS，算出这个机器人到每一个点的最短距离，
: 然后把所有机器人到该点的距离相加，得到最短的那个点。但是这样复杂度就很大了，
|
S********t
发帖数: 3431 | 4 I don't think either would work well
【在 f*********s 的大作中提到】
: 感觉是求所有点到所有点的最短距离，可以用bellman ford法。
: 另外，这个图看起来有点像8皇后，也许可以考虑回溯
|
w*x
发帖数: 3456 | 5 我有点思路，不知道能不能实现。
当一号机器人遍历的时候，如果到达另外一个机器人（2号），则2号机器人到1号机器
人路径上所有点的距离也就都有了，并且1号通过2号的到达的点到2号的距离也就都有
了。 |
k****r
发帖数: 807 | 6 don't think there is other better solution.
If the number of r is larger than the one of the empty, to calculate for
each empty position instead can work faster.
【在 y******s 的大作中提到】
: input：char[][] matrix, Point[] robots
: output: int
: 给一个矩阵，0代表可以通过，x 代表障碍物，不能通过，r代表机器人，求找出一点
: 使得所有机器人到该点的sum 最小
: 0 R 0 0 0
: 0 0 x R x
: x 0 R 0 x.
: 0 0 0 0 0
: 最直接的思路就是从一个机器人开始做BFS，算出这个机器人到每一个点的最短距离，
: 然后把所有机器人到该点的距离相加，得到最短的那个点。但是这样复杂度就很大了，
|
y******s
发帖数: 92 | 7 这是一个好主意，在面试的时候值得提出来，多谢
【在 k****r 的大作中提到】
: don't think there is other better solution.
: If the number of r is larger than the one of the empty, to calculate for
: each empty position instead can work faster.
|
