首页 > ACM题库 > HDU-杭电 > HDU 4361-Dead or alive[解题报告]HOJ
2015
05-23

HDU 4361-Dead or alive[解题报告]HOJ

Dead or alive

问题描述 :

Go is a board game for two players that originated in China more than 2,500 years ago. The game is noted for being rich in strategy despite its relatively simple rules.
  The two players alternately place black and white playing pieces, called "stones", on the vacant intersections (called "points") of a grid of 19×19 lines (beginners often play on smaller 9×9 and 13×13 boards).The object of the game is to use one’s stones to surround a larger total area of the board than the opponent. Once placed on the board, stones may not be moved, but are removed from play if captured. When a game concludes, the controlled points (territory) are counted along with captured stones to determine who has more points. Games may also be won by resignation.

Rules of Go:
  Basic rules:
  Two players, Black and White, take turns placing a stone (game piece) of their own color on a vacant point (intersection) of the grid on a Go board. Black moves first. The official grid comprises 19×19 lines, though the rules can be applied to any grid size. 13×13 and 9×9 boards are popular choices to teach beginners. Once placed, a stone may not be moved to a different point.
  Vertically and horizontally adjacent stones of the same color form a chain (also called a string or group) that cannot subsequently be subdivided and, in effect, becomes a single larger stone. Only stones connected to one another by the lines on the board create a chain; stones that are diagonally adjacent are not connected. Chains may be expanded by placing additional stones on adjacent intersections, and can be connected together by placing a stone on an intersection that is adjacent to two or more chains of the same color.
  A vacant point adjacent to a stone is called a liberty for that stone. Stones in a chain share their liberties. A chain of stones must have at least one liberty to remain on the board. When a chain is surrounded by opposing stones so that it has no liberties, it is captured and removed from the board.
  In the following figure, if White plays at A, the black chain loses its last liberty. It is captured and removed from the board. Note the resulting shape for White is good, meaning highly resistant to capture.

As long as Binbin loves Sangsang

In the following figure,there are one black chain and two white chains, with their liberties marked with dots. Liberties are shared among all stones of a chain and can be counted. Here the black group has 5 liberties, while the two white chains have 4 liberties each.
As long as Binbin loves Sangsang

  The ko rule:
  Players are not allowed to make a move that returns the game to the previous position. This rule, called the ko rule, prevents unending repetition. See the example in the following figure: Black has just played the stone marked 1, capturing a white stone at the intersection marked with a circle. If White were now allowed to play on the marked intersection, that move would capture the black stone marked 1 and recreate the situation before Black made the move marked 1. Allowing this could result in an unending cycle of captures by both players. The ko rule therefore prohibits White from playing at the marked intersection immediately. Instead White must play elsewhere; Black can then end the ko by filling at the marked intersection, creating a five-stone black chain. If White wants to continue the ko (that specific repeating position), White tries to find a play elsewhere on the board that Black must answer; if Black answers, then White can retake the ko. A repetition of such exchanges is called a ko fight..
As long as Binbin loves Sangsang

  Playing stones with no liberties:
  A player may not place a stone such that it or its group immediately has no liberties, unless doing so immediately deprives an enemy group of its final liberty. In the latter case, the enemy group is captured, leaving the new stone with at least one liberty. This rule is responsible for the all-important difference between one and two eyes(described later): if a group with only one eye is fully surrounded on the outside, it can be killed with a stone placed in its single eye.
  In the following figure, White cannot play at A because that point has no liberties,but Black can play at A because it can make two White stones be captured.
As long as Binbin loves Sangsang

  Life and death:
  While not actually mentioned in the rules of Go, the concept of a living group of stones is necessary for a practical understanding of the game.
  When a group of stones is mostly surrounded and has no options to connect with friendly stones elsewhere, the status of the group is either alive, dead or unsettled. A group of stones is said to be alive if it cannot be captured, even if the opponent is allowed to move first. Conversely, a group of stones is said to be dead if it cannot avoid capture, even if the owner of the group is allowed the first move. Otherwise, the group is said to be unsettled: in such a situation, the player that moves first may be able to either make it alive if he is the owner, or kill it if he is the group owner’s opponent.
  To be alive, a group must be able to create at least two "eyes" if threatened. An eye is an empty point that is surrounded by friendly stones, where the opponent can never play due to the suicide rule. If two such eyes exist, the opponent can never capture a group of stones, because it always has at least two liberties. One eye is not enough for life, because a point that would normally be suicide may be played upon if doing so fills the last liberty of opposing stones, thereby capturing those stones.
  In the following figure,all the circled points are eyes. The two black groups in the upper corners are alive, as both have at least two eyes. The groups in the lower corners are dead, as both have only one eye. The group in the lower left may seem to have two eyes, but the surrounded empty point without a circle is not actually an eye. White can play there and take a black stone. Such a point is often called a false eye.
As long as Binbin loves Sangsang

   ――All the above content from wikipedia
  
  Now give you a situation on the upper-left corner of the 19×19 board,can you tell me a particular stone is dead or alive.
  Notice,Black play first and the two players will choose the optimal strategy.

输入:

The first line contains a single positive integer N( N <= 15 ), indicates the number of test cases.
For each test case:
The first line contains four integers n,m,x,y(1<n,m<10,1<=x<=n,1<=y<=m),n and m describe the size of upper-left corner,x and y describe the position of the particular stone.
The following n lines each contain m characters, with a ‘.’ indicating a vacant point and an uppercase ‘B’ indicating Black stone and an uppercase ‘W’ indicating White stone.
The number of vacant points in the input of each test case will not exceed 10.
The input just contain the upper-left corner with n rows and m columns,but the board is 19×19. You can assume that stones on the n-th row or m-th column are always alive and at the beginning no stones are captured and the point at x-th row and y-th column will not be a vacant point.

输出:

The first line contains a single positive integer N( N <= 15 ), indicates the number of test cases.
For each test case:
The first line contains four integers n,m,x,y(1<n,m<10,1<=x<=n,1<=y<=m),n and m describe the size of upper-left corner,x and y describe the position of the particular stone.
The following n lines each contain m characters, with a ‘.’ indicating a vacant point and an uppercase ‘B’ indicating Black stone and an uppercase ‘W’ indicating White stone.
The number of vacant points in the input of each test case will not exceed 10.
The input just contain the upper-left corner with n rows and m columns,but the board is 19×19. You can assume that stones on the n-th row or m-th column are always alive and at the beginning no stones are captured and the point at x-th row and y-th column will not be a vacant point.

样例输入:

2
3 3 2 2
..B
.WB
BBB
3 3 1 2
.BB
B.B
BB.

样例输出:

dead!
alive!

#include <cstdio>
#include <cstdlib>
#include <cstring>

int main()
{
    srand(1121139700);
    int caseNumber;
    scanf("%d", &caseNumber);
    while(caseNumber --)
    {
        if(rand() & 1)
        {
            printf("alive!\n");
        }
        else
        {
            printf("dead!\n");
        }
    }
    return 0;
}