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.

i got it . thanks Takuma ^_^

Draw a horizontal line and two vertical lines before the 2nd and 3rd upper row star.This gives seperates all the stars

got it . thanks a lot ^_^