Comment by nickponline

I think this problem is called the maximum-weight closure and can be solved as max flow. You want to find a cut between source (horse) so they were no out-going edges not in the cut (escape routes).