※ 引述《iamnotgm (伽蓝之黑)》之铭言：
: 问题是这样的
: 座标平面上有几个炸弹
: 每个炸弹引爆时会炸出一个正方形的范围
: 任何在这个范围内的其他炸弹会连锁反应一起炸
: 给定N个炸弹的位置和爆炸范围后
: 求点燃最少的炸弹把所有的炸弹炸光
: 我的解法是先找出每一颗炸弹可以炸到谁
: 做出一张graph后找出不会被其他人炸到的炸弹先炸
: 炸完后剩下来还没引爆的炸弹应该就是存在于环上
: 先假定引爆A炸弹
: 之后如果再引爆B炸弹发现他会点燃A炸弹就把A炸弹拿掉
: 直到所有的炸弹都被主动或被其他炸弹引爆
: 这个样子的解法会wrong answer
: 但是我想不出来有什么样的case是我的算法没考虑到的
试试看
3
6 4 1
4 4 4
8 4 4
根据你第二步选出 A 炸弹的方法, 可能要把输入顺序调换一下.
无论如何, 这个测资长这样
_______________
| | _ | |
| B |A| C |
|____|_____|____|
也就是 B, C 会互相引爆, 也都会引爆 A, 但是 A 爆炸不会有连锁反应
因此问题出在这一句:
炸完后剩下来还没引爆的炸弹应该就是存在于环上
应该要修正为:
炸完后剩下来还没引爆的炸弹应该就是存在于环上,
或者会被环上任一个炸弹的连锁反应引爆
因此第二步要确定引爆的 A 炸弹
1. 确实在环上
不过这样还不太够, 考虑下面这个 graph
C -> A
^ ^
| |
v v
D B -> E
上面那个条件确保我们不会选到 E, 但是我们仍然可能选到 A 或 B
(正解为引爆一次, C 或 D, 引爆 A, B, 或 E 都需要两次以上)
因此还需要第二个条件
2. 不会被另一个环上任一个炸弹的连锁反应引爆
到这里有没有发现第二步和第一步几乎一模一样, 只不过把‘炸弹’换成‘环’?
(第一步的两个条件是:
1. 确实是一个炸弹
2. 不会被另一个炸弹引爆
)
因此我们可以把图上每个环视为一个大炸弹, 然后数数看有几个 (大) 炸弹不会
被连锁反应炸到, 需要手动引爆, 就是答案了.
这么一来问题就变成, 要怎么找出所有的‘环’呢?
要注意所谓的‘环’不一定是一个圈喔!
A <- B -> D
| ^ |
| | |
+