Can someone help me how to solve this problem.I use greedy algorithm,every time I find the point which can destroy most rocks,but it wrong answer. I cannot find what data make the solution WA. Can someone tell me how to solve it?
thanks in advance!
Greedy is incorrect. Solution is optimized search. There is O(2^n) search algorithm which fits in time limit.
I thought of a 2^25 times 25 algo. Will it pass the limit ?
001000
000100
010010
Here are four "greediest" points at first move, I think, but two of them lead your algorithm to wrong way with three bombs instead of two.
You can solve this problem using Hungarian algorithm.
http://en.wikipedia.org/wiki/KM_algorithm
yeah.May be dancing links will solve it?