URI Online Judge | 1404

MegaCheckers

By Ricardo Anido Brazil
Timelimit: 1

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.

Input

The input contains several test cases. The first line of a test case contains two integers N and M, indicating, respectively, the number of lines and the number of columns of the board (3 ≤ N ≤ 20, 3 ≤ M ≤ 20 and N x M ≤ 200). The square at the bottom left corner of the board is a house. The second line contains a description of the match state. Each description consists of [(N x M)/2] integers, separated by a space, corresponding to the boards houses, that are numbered from 1 to [(N x M)/2], from the left to the right, from the nearest edge from the player to the nearest edge from the opponent. On the state match description, ‘0’ represents an empty house, ‘1’ represents a house with one of your pieces, and ‘2’ represents a house with an opponent’s piece. There are, at most, [(N x M)/4] pieces of each player on the board. The input final is indicated by N = M = 0.

Figure 1: House’s numerations in (a) board of dimensions 8 x 8 and in (b) board of dimensions 5 x 3.

Output

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

Sample Input Sample Output

3 3
2 1 2 0 1
5 3
1 0 2 1 0 2 0 0
8 8
2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2 0 1 0 0
0 0

1
2
7