I was solving the problem set of Code forces when I stumbled upon this question Protect Sheep. The question was pretty simple if we simply place dogs on all the empty spots.

But if we were supposed to minimize the number of the dogs used to protect the sheep. How do we solve it then? There seems to be many cases to handle. Any kind of help would be appreciated!

Maybe I have an idea,don't know this would work or not.....if not please tell me what is wrong here.....

first i would place dogs around all sheeps and count them =count_1....(so that all sheeps are safe) then again i traverse the whole grid and place dogs around all wolves =count_2.....(so thar wolfes can't go anywhere).... answer would be the min(count_1,count_2)...........

Suppose all sheep are on one side and all wolves on the other side, we can put dogs in the between them. That can have less number of dogs in many cases of r and c. I think you get the idea.

yes i got it

max flow, min cut

Thats a 900 rated problem -_-

Yeah and OP asked for a different version of it.

I think I didn't understand how to use max flow-min cut to solve the optimization problem. Could you elaborate it more?

Are you suggesting to connect all the sheep with all the wolves with an edge capacity of one and then find the Min-Cut. If yes, how would you model the case where you four sheep are placed at the corners of the field and yo have sheep at the center?