Beth and Benny are playing a board game that is similar to checkers. The game is played on an board. In one move, Beth can capture Benny's piece if it is diagonally adjacent (in any of the four directions) to one of her pieces by jumping over it with one of her own pieces, provided that the square directly over Benny's piece exists and is empty. The captured piece is then removed from the board. Multiple captures can be made in the same move, provided that Beth always moves the same piece and a piece is captured after every jump. Beth wants to know the maximum number of Benny's pieces that she can capture in a single move!
Input Specification
The input will contain lines, each with characters, representing the board.
.
denotes an empty square.A
denotes one of Beth's pieces.B
denotes one of Benny's pieces.
Output Specification
Output the maximum amount of pieces that Beth can capture in a single move.
Sample Input 1
.B.B.B.B
B.B.B...
.B.B...B
....B...
.A.....A
A...B...
.A.A.A.A
A.A.A.A.
Sample Output 1
2
Explanation for Sample 1
The piece on square f2 can hop to d4 and then to f6, capturing the pieces on e3 and e5 respectively.
Note that the piece at e7 cannot be captured because e8 is occupied by another piece.
Sample Input 2
........
........
.B.B.B..
........
.B.B.B..
........
.B.B.B..
..A.....
Sample Output 2
7
Explanation for Sample 2
The piece on square c1 can capture 7 pieces and end on a7, as shown in the image below.
Comments