3116：MegaCheckers

MegaCheckers is a board game for two players, very similar to the known game of Checkers. The board is rectangular, with N rows and M columns of small squares arranged in an N × M grid. The small squares are alternatingly colored with a light color and a dark color, in the usual standard of a checkers board. The squares of dark color are calls “homes” (note however that, for visualization reasons, the figures below show homes as white squares).

At the beginning of the game, each player has a certain number of pieces, placed in homes closest to the edge of the board the player chooses (the players choose opposite edges). During the game, the pieces can only occupy the homes of the board.

One of the moves of the game is to “capture” an opponent’s piece, jumping over it, diagonally, to an adjacent home beyond the piece, which should be empty. The opponent’s piece is then removed from the board. The three homes involved in the capture (the initial home of your piece, the home that holds the opponent’s piece and the empty home, where your piece will be after the play) must be diagonally aligned and diagonally adjacent, as in the figure below.

Simple capture	Multiple capture

In MegaCheckers a piece can capture the opponent’s pieces jumping diagonally forward or backward (note that, in the majority of existent variants of the game of checkers, a piece can only capture opponent pieces jumping forward). You can also trigger a multiple capture, with just one piece, jumping successively to empty homes over opponent pieces. In a multiple capture, your piece can change direction, jumping in one direction and later in another one. You can capture only one piece each jump, but can capture several pieces with successive jumps. You can’t jump over a piece of yours, or jump over the same opponent piece more than once.

The dimensions of the board and a description of the current state of a game are given. It’s your turn to play and you should determine of maximum number of your opponent’s pieces that can be captured in one capture move.

The input contains several test cases. The first line of a test case contains two integers N and M indicating respectively the number of rows and the number of columns of the board (3 ≤ N ≤ 20, 3 ≤ M ≤ 20 and N × M ≤ 200). The leftmost square of the board at the edge closest to the player is a home. The second line contains the description of the state of the game. Each description consists of ceiling((N × M) ⁄ 2) integers, separated by a space, corresponding to the homes of the board, which are numbered from 1 to ceiling((N × M) ⁄ 2), from left to right, from the edge closest to the player to the edge closest to his opponent. In the description of the state of the game, ‘1’ represents a home with a piece of yours, and ‘2’ represents a home with a piece of your opponent’s. There are at most floor((N × M) ⁄ 4) pieces of each player on the board. The end of the input is indicated by N = M = 0.

(a)	(b)

Figure 1: Numeration of homes on (a) board of dimensions 8 × 8 and on (b) board of dimensions 5 × 3.

For each test case, your program should produce one line of output, containing an integer indicating the largest number of pieces of your opponent’s that can be captured in one move.