American Computer Science League: 2008/09 Contest #4

Reversi (Senior)

According to Wikipedia, Reversi (also known as Othello) is an abstract strategy board game which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. Pieces have an X on one side and an O on the other side, each side representing one player. The object of the game is to make your pieces constitute a majority of the pieces on the board at the end of the game, by flipping as many of your opponent's pieces as possible. At the start of every game the pieces are placed as in the figure in upper left.

  A B C D E F G H
8                
7                
6                
5       X O      
4       O X      
3                
2                
1                
  A B C D E F G H
8                
7                
6         #      
5       X O #    
4     # O X      
3       #        
2                
1                
  A B C D E F G H
8                
7                
6         X      
5       X X      
4       O X      
3                
2                
1                
  A B C D E F G H
8                
7                
6       # X #    
5       X X      
4       O X #    
3                
2                
1                

X goes first. X tries to (but does not have to) place a piece with the X side up on the board next to an O, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) line between the new piece and another X piece, with one or more contiguous O pieces between them. In the figure in the upper right, X has the options indicated by #'s if he decides to flip a piece.

After placing the piece, X flips over all O pieces lying on a straight line between the new piece and any anchoring X pieces. All flipped pieces now show the X side, and X can use them in later moves — unless O has flipped them back in the meantime.

If X decided to place the piece at location 6E, the result would be as in the figure on the lower left. Now, it's O's turn to play. O can put a piece at any of the locations indicated with a # as shown in the figure on the lower right.

Input

There will be 5 input lines. Each line will give the position of the pieces played (in X – O order) after the initial start pieces are placed. That is the four pieces shown in the upper-left figure are on the board at the start of each input line. Each line will have a series of 2-character locations in row-column order. The last location on each line will be ## signifying the end of the data.

Output

For each line of input, print the total number of pieces that were flipped.

Sample Input (note: only 4 lines shown)

5F 6D 5C 5G 4C 5B ##
4C 4F 5F 4B 4G 5G 4A ##
3D 6D 5F 2D 7D 5G 1D ##
6D 3D 4F 6E 7D 2D ##

Sample Output

8
10
12
1

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...