The last test case was one where one centrally planted bomb would wipe out most of the targets, but the remaining targets were too scattered to take out with the few bombs you had left. I ran out of time on this one, but I came up with a scheme to use:
To deal with the last test case, we need to plan ahead.
For each position on the grid, scan for spy nodes.
If we find any at all, make a copy of the map and mark the blast radius.
If we have enough to deploy at all locations, go ahead on.
Otherwise we have a problem.
Now we combine (bombs) number of blast maps to find one that will eliminate all
We OR (bomb) number of blast locations together, then
compare with original to see if any nodes are left. This requires exhaustive
combinations of all the premutations of blast maps.
When we have our list, then we need to schedule our bombs.
We can do this by simply restricting our normal scan to locations from our list.
Each time a bomb is placed it is stricken from our list.
Since there is only 15 minutes left, I doubt I will be able to complete it in time.
I've done enough of these problems I should have planned ahead better, but where's
the fun in that? Much more to fun to just try and bull your way through. I mean,
I'm not getting paid, and planning ahead is lot like work.