i tried to solve this problem in the contest time but it gave me a WA . today i try to understand why my answer is wrong .i used an accepted code and try some test cases ... one of them was :
so it locks like :
and the the fences should (i think) be like :
so my answer is 5 ... but the Accepted code output is 3 !
i can't understand how to but only 3 fences to prevent the snakes communicate with each other . can any one explain this problem to me ?
thanks in advance .
UPD: the optimal solution for the above sample :
Thanks :)
If you use a horizontal line, you split the grid into a top and bottom compartment of size 6. Then if you place a vertical line after the 2nd and 4th snakes, you end up with 6 compartments of size 2. So with just three lines you can split each snake into their own compartment.
Draw a horizontal line and two vertical lines before the 2nd and 3rd upper row star.This gives seperates all the stars