問題是這樣的
座標平面上有幾個炸彈
每個炸彈引爆時會炸出一個正方形的範圍
任何在這個範圍內的其他炸彈會連鎖反應一起炸
給定N個炸彈的位置和爆炸範圍後
求點燃最少的炸彈把所有的炸彈炸光
我的解法是先找出每一顆炸彈可以炸到誰
做出一張graph後找出不會被其他人炸到的炸彈先炸
炸完後剩下來還沒引爆的炸彈應該就是存在於環上
先假定引爆A炸彈
之後如果再引爆B炸彈發現他會點燃A炸彈就把A炸彈拿掉
直到所有的炸彈都被主動或被其他炸彈引爆
這個樣子的解法會wrong answer
但是我想不出來有什麼樣的case是我的演算法沒考慮到的
上網查了一下看到了一個解法叫做strongly connected component
可是我不懂這東西和這題的關聯性
題目連結:
https://icpcarchive.ecs.baylor.edu/external/48/4846.pdf
先謝過各位了