问个面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个面试题

问个面试题# JobHunting - 待字闺中

y*s2015-11-07 08:11

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*s2015-11-07 08:11

2 楼

自顶，求思路

f*s2015-11-07 08:11

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*t2015-11-07 08:11

4 楼

I don't think either would work well

【在 f*********s 的大作中提到】

: 感觉是求所有点到所有点的最短距离，可以用bellman ford法。
: 另外，这个图看起来有点像8皇后，也许可以考虑回溯

w*x2015-11-07 08:11

5 楼

我有点思路，不知道能不能实现。
当一号机器人遍历的时候，如果到达另外一个机器人（2号），则2号机器人到1号机器
人路径上所有点的距离也就都有了，并且1号通过2号的到达的点到2号的距离也就都有
了。

k*r2015-11-07 08:11

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 的大作中提到】

y*s2015-11-07 08:11

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.