请教一道snapchat的小车雷达题

厉害的超人 发表于 2016-9-18 02:21
前面czhoume已经给出了解答，重叠的圆圈都group起来，使用union-find就行了。
先给出具体解答，可能有bu ...

感谢回复，我觉得这种做法是没有问题的。我是觉得这题应该也可以用merge interval来解

jy_121 发表于 2016-9-18 02:50
感谢回复，我觉得这种做法是没有问题的。我是觉得这题应该也可以用merge interval来解

嗯嗯，同感，感觉可以把所有圆y的范围表示成interval，然后merge后，查看是0~1是否全部cover了

神罗天征 发表于 2016-9-18 07:15
嗯嗯，同感，感觉可以把所有圆y的范围表示成interval，然后merge后，查看是0~1是否全部cover了

想了下还是不能一下merge全部的，总体0-1都覆盖的话还是可以走的

jy_121 发表于 2016-9-18 07:19
想了下还是不能一下merge全部的，总体0-1都覆盖的话还是可以走的

哦哦，懂了，可能x相差很远，但是y merge了后覆盖0-1对吧，多谢提醒

这样做是有问题的。投影过后的区间覆盖[0,1]并不能保证小车一定不能通过
|    ======|
|    ======|
|    ======|
|    ======|
|                 |
|             |
|====       |
|====       |
|====       |
|====       |
|             |
把上面的方块想象成圆即可。


正确做法是反过来考虑，判断小车会不会被堵死。
先建图，每个圆是一个点，路的左右两侧各对应一个点，两圆相交则连边，圆和两侧相交也连边。那么小车会被堵死当且仅当有从左侧到右侧的路径。

mark一下