Othello

Interview

Time limit1sMemory limit128 MB

Summary

Simulate up to 30 Othello moves on an 8x8 board starting from one of three configurations, then print the final black and white disc counts.

Level: Medium4 of 10
Topics: Simulation, Implementation, Matrix, Array
Solved: No attempts yet

Problem

Othello (also known as Reversi) is played on an $8 \times 8$ board. Each square is identified by its row and column: the top row is row 1 and the left column is column 1. Discs are black on one side and white on the other; one player places discs black-side up and the other white-side up.

The game starts with some discs already on the board.

A move is valid when both of the following hold:

The disc is placed on an empty square that is adjacent — horizontally, vertically, or diagonally — to a disc already on the board.
It flips at least one of the opponent's discs. After placing a disc, look outward along each of the eight directions (horizontal, vertical, diagonal). If a straight, unbroken line of opponent discs is bounded on its far end by one of your own discs, every opponent disc on that line is flipped to your colour. A direction flips nothing if an empty square or the board edge is reached before one of your own discs.

Black always moves first, then the players alternate white, black, white, and so on. Simulate the given sequence of moves and report how many discs of each colour are on the board at the end.

Input

The input consists of three parts.

First, a single letter (a, b, or c) giving the initial board configuration:

Configuration a: the standard Othello start. Squares (4,4) and (5,5) are white; (4,5) and (5,4) are black.
Configuration b: the main-diagonal squares (1,1), (2,2), …, (8,8) are all black; the anti-diagonal squares (1,8), (2,7), …, (8,1) are all white.
Configuration c: columns 3 and 4 are entirely black, and columns 5 and 6 are entirely white (across all 8 rows).

Configuration `a`	Configuration `b`	Configuration `c`

Next, an integer $n$ with $0 \le n \le 30$ : the number of moves to simulate. Then follow $n$ pairs of integers $R$ $C$ with $1 \le R \le 8$ and $1 \le C \le 8$ , where $R$ is the row and $C$ the column of each move, in order.

The first move is black's, the second white's, the third black's, and so on. Every listed move is guaranteed to be a valid move on an empty square.

Output

Print two integers separated by a single space: the number of black discs, then the number of white discs, after all moves have been made.

Examples3

Example 1
Input
```
a 1 5 6
```
Expected output
```
4 1
```
Example 2
Input
```
b 0
```
Expected output
```
8 8
```
Example 3
Input
```
c 3 1 7 2 2 2 1
```
Expected output
```
22 13
```