MegaCheckers

MegaCheckers is a board game for two players, very similar to the known Checkers game. The board is rectangular, with N lines and M columns of small squares arranged in a grid N x M. The small squares are alternately colored with a bright color and a dark color, on the usual standard of a checker’s board. The squares of dark colors are denominated “houses” (notice that, for visualization reasons, the diagrams below show houses as white squares).

At the beginning of the match, each player has a certain number of pieces, positioned on the nearest houses from the board edge that the player chose (the players choose opposite edges). During the match, the pieces can only occupy the houses on the board.

One of the movements of the game is “capture” an opponent piece, jumping over it, diagonally, to the adjacent house through the piece, house that should be empty. The opponent piece is so removed from the board. The three involved houses on the capture (your piece’s initial house, the house that contains the opponent’s piece and the empty house, where your piece will be after the move) should be diagonally aligned and must be diagonally adjacent, as shown in the diagram below.

In MegaCheckers a piece can capture opponent’s pieces jumping diagonally forward or backward (notice that, on the existents variations of the Checkers game, a piece can only capture opponent’s pieces jumping forward). You may also make a multiple capture, with one piece only, then jumping to empty houses over opponent’s pieces. In a multiple capture, your piece may change direction, jumping first in one direction and then in another. You can capture just one piece in each jump, but can capture several pieces with sequentially jumps. You can’t jump over a piece of yours, and can’t jump the same opponent’s piece more than once.

It’s given the board dimensions and a description of the current match state. It is your turn to play and you must determine the maximum number of opponent’s pieces that can be captured in a capture movement.