2015
04-16

# Abalone

Abalone is a popular board game, the rules are as follow:
1.At first, two players each have 14 marbles, starting to play in turn.

2.For each turn, player must move a line of one, two or three adjacent marbles one space unless he couldn’t move any marbles. The move can be either in-line (parallel to the line of marbles)

or broadside (not parallel to the line of marbles), as illustrated below.

3.A player can push their opponent′s marbles which are in an adjacent space to their own with an in-line move only. They can only push if the pushing line has more marbles than the pushed line (three can push two or one; two can push one). Marbles must be pushed into an open space or out of board(i.e. not blocked by a marble of either colour).

4.The winner is the first player to push six of the opponent’s marbles off of the edge of the board.

Now, it’s White player’s turn to move, could White player win in this turn? If not, Black player moves, could Black player win in next turn no matter which move White player choose?

The first line is a number T(1<=T<=30), which represents the number of case. The next T blocks follow each indicates a case.
A block has nine lines. They are the state of the situation.
‘B’ indicate the Black marble.
‘W’ indicate the White marble.
‘.’ indicate blank.
The number of marbles for each color will be no bigger than 14 and no smaller than 9.

The first line is a number T(1<=T<=30), which represents the number of case. The next T blocks follow each indicates a case.
A block has nine lines. They are the state of the situation.
‘B’ indicate the Black marble.
‘W’ indicate the White marble.
‘.’ indicate blank.
The number of marbles for each color will be no bigger than 14 and no smaller than 9.

3
B B B B B
B B B B B B
. . B B B . .
. . . . . . . .
. . . . . . . . .
. . . . . . . .
. . W W W . .
W W W W W W
W W W W W

. . . . .
B B B B B B
. W B B B . .
. . W . . . . .
. . . W . . . . .
. . . . . . . .
. . . . . . .
W W W W W W
W W W W W

. . . . .
W B B B . .
W W B B B . .
W . W B B B . .
W W W W . . . . .
. . . . . . . .
. . . . . . .
. . . . . .
. . . . .

Case 1: Draw
Case 2: White
Case 3: Black

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

3. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}