问题是这样的
座标平面上有几个炸弹
每个炸弹引爆时会炸出一个正方形的范围
任何在这个范围内的其他炸弹会连锁反应一起炸
给定N个炸弹的位置和爆炸范围后
求点燃最少的炸弹把所有的炸弹炸光
我的解法是先找出每一颗炸弹可以炸到谁
做出一张graph后找出不会被其他人炸到的炸弹先炸
炸完后剩下来还没引爆的炸弹应该就是存在于环上
先假定引爆A炸弹
之后如果再引爆B炸弹发现他会点燃A炸弹就把A炸弹拿掉
直到所有的炸弹都被主动或被其他炸弹引爆
这个样子的解法会wrong answer
但是我想不出来有什么样的case是我的算法没考虑到的
上网查了一下看到了一个解法叫做strongly connected component
可是我不懂这东西和这题的关联性
题目连结:
https://icpcarchive.ecs.baylor.edu/external/48/4846.pdf
先谢过各位了