首页 > ACM题库 > HDU-杭电 > hdu 4062 Abalone待解决[解题报告]C++
2015
04-16

hdu 4062 Abalone待解决[解题报告]C++

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.
A Card Game

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)
A Card Game

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

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).
A Card Game

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


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  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));
    }
    }

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。