请问这是说我邮寄的140材料收到了?# Immigration - 落地生根
z*f
1 楼
有这样一些点:
a1 a2
b1 b2 b3
c1 c2 c3
现在手里面有map知道每个点的edges,比如这样:
a1->b1
a2->b1
a2->b2
a2->b3
b1->c1
b2->c2
b2->c3
b3->c3
然后Input知道第一层有哪些点是有用的,比如a2;也知道最后一层哪些点是有用的,比
如c2和c3;然后中间有些点是不能经过的,这里比如b2。
现在需要打印从第一层有用的点到最后一层中间可以经过的点(包括第一层和最后一层
有用的点本身),一个点只用打印一次。比如这个例子就应该打印:
a2 b3 c3
我尝试了一会用graph search+DFS找到所有路径,每条路径是一个array,然后把每条
路径的所有点存起来,最后把重复的点再删除掉,不过写了一会就没信心放弃了,
performance太糟糕了。然后想了想能不能用dp,比如bottom up,每到一个node就把
所有通向该node的邻近nodes通通找出来,但是我不知道这个跟暴力搜索相比优化在哪
里。
请大牛提供一下思路或者解法,非常感谢。
a1 a2
b1 b2 b3
c1 c2 c3
现在手里面有map知道每个点的edges,比如这样:
a1->b1
a2->b1
a2->b2
a2->b3
b1->c1
b2->c2
b2->c3
b3->c3
然后Input知道第一层有哪些点是有用的,比如a2;也知道最后一层哪些点是有用的,比
如c2和c3;然后中间有些点是不能经过的,这里比如b2。
现在需要打印从第一层有用的点到最后一层中间可以经过的点(包括第一层和最后一层
有用的点本身),一个点只用打印一次。比如这个例子就应该打印:
a2 b3 c3
我尝试了一会用graph search+DFS找到所有路径,每条路径是一个array,然后把每条
路径的所有点存起来,最后把重复的点再删除掉,不过写了一会就没信心放弃了,
performance太糟糕了。然后想了想能不能用dp,比如bottom up,每到一个node就把
所有通向该node的邻近nodes通通找出来,但是我不知道这个跟暴力搜索相比优化在哪
里。
请大牛提供一下思路或者解法,非常感谢。