Task: Peg Removal (Network flow algorithm)

We have a few pegs placed in a line of twelve holes. We want to remove pegs by jumping over other pegs. Jumped over pegs disappear as a result of a move. A move is possible if there is a straight line of three adjacent holes, where two adjecent holes contain a peg and the third is empty. The outside peg may jump over the middle peg and be placed in the vacant hole on the other outside position. To illustrate these moves consider the following figure (black nodes are pegged holes). Peg at position 8 jumps to the hole at position 6 then the peg at position 5 jumps past the peg at position 6 and ends up at position 7.

Your goal is to find a sequence of moves such that as few pegs as possible are left. The input consists of several cases. The first line is an integer denoting how many. The subsequent lines are text strings of 12 characters in length consisting of - (minus) and o (little oh). An o represents an peg and an - represents an empty hole. Output an integer denoting the smallest number of remaining pegs obtained by some sequence of moves.

Sample Input: 5 --ooo--oo--- ooooo-----oo oooooooooooo -o-----oo--- -oo-oo-oo--- Sample Output: 2 4 12 2 2

Program has to be efficient and have a runtime under 1 second.