Buttercola: Zenefits: Robert Merge Point
Zenefits: Robert Merge Point
一个matrix, 1代表机器人,0代表通路,x代表路障,求到所有机器人距离和最小的一点
需要注意的是机器人本身也是通路的一部分,可以通过他到达其他机器人,甚至最小点
也可以和机器人在同一个点上。. from: 1point3acres.com/bbs
另外如果被路障围起来的点不能被算进来
Solution:
Note that this problem like mini distance can only be solved by using BFS, not DFS.
We need to handle when to mark the visited[][] as false. In this question, we simply that for each tracking, we define a new boolean[][ visited.
需要注意的是机器人本身也是通路的一部分,可以通过他到达其他机器人,甚至最小点
也可以和机器人在同一个点上。. from: 1point3acres.com/bbs
另外如果被路障围起来的点不能被算进来
*//problem: robot merge point
//input:
//robot: 1
//obstacle: X
[
0 0 0 M 1
0 1 X 0 0
0 X 0 0 0
0 0 0 1 0
0 0 0 0 0
//output:
//best merge point: M
3 + 1 + 3 = 7
. from: 1point3acres.com/bbs Definition: Best merge point: minimal sum of path num between robots and merge point*/
Solution:
Note that this problem like mini distance can only be solved by using BFS, not DFS.
We need to handle when to mark the visited[][] as false. In this question, we simply that for each tracking, we define a new boolean[][ visited.
Read full article from Buttercola: Zenefits: Robert Merge Point
No comments:
Post a Comment