PROBLEM STATEMENT
Go is an ancient game for two players, who alternate placing stones on a 9x9
grid, black first. Given a sequence of plays of both players, return the number
of stones captured during the game by each player.
If two stones of the same color are placed adjacent to each other horizontally
or vertically ("adjacent" never means diagonally in this problem), they form
one "group" and are considered one entity for the remainder of the game.
Likewise, placement of additional stones may cause two groups to join into one
group, or may cause one group to be extended.
Each group has some number of "liberties": each unoccupied space adjacent to a
member of the group counts as one liberty. If a player plays a stone in such a
way that an opponent's group has zero liberties, the opponent's group is
killed, and the player is credited with one point for each stone in the killed
group.
Some examples of liberty counting: ('X' represents black stones, 'O' represents
white stones, and '.' is empty space.)
....
.OO.
....
The 'O' player's group has six liberties; two on the top, two on the bottom,
one on the left, and one on the right.
.....
O....
OX...
OX...
OX...
The 'O' player's group has only two liberties (the edge of the board does not
count as unoccupied space).
The 'X' player's group has 4 liberties: three on the right, and one on the top.
....
..X.
.XO.
..X.
....
The 'O' player's group has only one liberty, to the right. If the 'X' player
moved there, the single 'O' stone would be removed from the board, and the 'X'
player would score a point.
....
XX..
OOX.
.OX.
The 'O' player's group has only one liberty, to the lower left. That group does
*not* have a liberty in the upper right corner, because it is only connected
via a diagonal.
If the 'X' player moves in the lower left corner, the three 'O' stones are
removed (killed), and 'X' scores 3 points. Note that this is a legal move for
X, even though he is moving into a space that gives him no liberties, the death
of the 'O' group is resolved before the fate of his current move. If the 'O'
group had an additional liberty, it would be illegal for 'X' to move in the
lower left corner, because the 'O' group would not die, and X's move would be
suicide, which is not allowed unless it results in a group being killed first.
Each stone's position on the 9x9 board is specified by a letter ('A' to 'I')
specifying the row, and a number ('1' to '9', inclusive) specifying the column.
See the examples for more details.
DEFINITION
Class: Go
Method: count
Parameters: String[], String[]
Returns: int[]
Method signature (be sure your method is public): int[] count(String[]
blackMoves, String[] whiteMoves);
NOTES
- To those who know the full rules of Go: this problem does not use passes, ko,
komi, end-of-game territory counting, and groups are never removed unless they
have zero liberties.
- The edge of the board does not count as either player's stones, and no stone
has a liberty in the edge of the board.
- The board is fixed at 9x9.
- Black's score should be returned at index 0 of the int[], and white's score
should be returned at index 1 of the int[].
- It is legal to move in an empty space where a previous stone was captured (as
long as it's not a suicide move). Therefore the same String may exist more than
once in the inputs. See the last example.
- If you place a stone in a suicide position that kills opponents' stones, they
disappear but your stone does not.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- blackMoves has either the same number of elements as whiteMoves, or one more
than whiteMoves.
- blackMoves and whiteMoves will each contain 0 to 50 elements, inclusive.
- each String consists of a single capital letter ('A' to 'I' inclusive)
followed by a number ('1' to '9' inclusive), representing the space on the
board in which the stone is played.
- Each move will be legal, that is, no stone will be placed where another
currently exists.
- No stone will be placed into suicide unless it also kills an opposing group.
EXAMPLES
(Remember that each move is its own String. Use the ++ option in the String[]
creator box to translate comma-delimited input into a String[].)
Input: blackMoves = {A2,B1}
whiteMoves = {A1}
Black first moves to A2, then white moves to A1. At this point, the board looks
like this:
At the end of At the end of
the first move: the second move (white's first move):
123456789 123456789
A .X....... A OX.......
B ......... B ......... (X is the black stone,
C ......... C ......... O is the white stone)
D ......... D .........
E ......... E .........
F ......... F .........
G ......... G .........
H ......... H .........
I ......... I .........
On black's second move, B1, the third overall move, he captures the white stone
at A1, since that stone no longer has any liberties.
123456789
A .X.......
B X........
C .........
D .........
E .........
F .........
G .........
H .........
I .........
Therefore black has one point and white has none; the method should return {1,0}.
Input: blackMoves = {E1,C1,C2,D3,G1,G2,F3,E4,E1}
whiteMoves = {D1,E2,D2,F1,F2,E3,G3,C3}
White's fourth move, F1, captures the black stone at E1. Immediately before
black's last move (after white's C3), the board looks like this:
123456789
A .........
B ......... (X = black)
C XXO...... (O = white)
D OOX......
E .OOX.....
F OOX......
G XXO......
H .........
I .........
Black's last move, E1, takes the last liberty of the large white group, killing
the pieces at D1,D2,E2,E3,F1,F2, giving black 6 points. The white pieces at C3
and G3 are not killed; they were not connected to the large group since they
only touched on a diagonal.
Returns {6,1}.
Input: blackMoves = {A1,B1,D1,E1,C2,C3}
whiteMoves = {A2,B2,D2,E2,F1,C1}
Output: {0,4}