408302: GYM103091 B Dots and Boxes

Alice and Bob are engaged in a Stanford vs. Berkeley board game tournament! This round, they are playing Dots and Boxes. However, both had amnesia and lost track of who won each game. The good thing is, they wrote down a record of the sequence of moves played.

Given a sequence of moves from the game Dots and Boxes, determine which player made each move, and the score at the end of the game.

Alice and Bob play a game of dots and boxes, with Alice playing first.

Dots and Boxes is played on a square grid of dots. Play alternates, with each player connecting two adjacent dots with a vertical or horizontal line. If a player completes a square by drawing the fourth line of one or more of the 1x1 squares, the player marks the box with their name and must then make another move. Whoever completes the most unit squares wins.

The first line of input contains a single number, $$$n$$$, which is the horizontal and vertical size of the square of dots ($$$3 \le n \le 10)$$$. Following this is a sequence of moves, one per line, specified as the coordinates of the dots connected by each move. Each move is given as four integer values $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ with all coordinate values between 1 and $$$n$$$, inclusive. The two dots described will always be adjacent; that is, $$$|x_1-x_2|+|y_1-y_2|=1$$$.

There will always be exactly $$$2n^2-2n$$$ moves; that is, every possible line will be drawn by the end of the game.

Your output will consist of two lines. The first line will contain a string with $$$2n^2-2n$$$ characters indicating who made the corresponding move, and in what order. A move made by Alice will be indicated by the character 'A' and a move made by Bob will be indicated by the character 'B'.

The second line will contain two integer values, giving the final score of the game. The first value will be Alice's score, and the second will be Bob's score. The sum of these two numbers should always sum to $$$(n-1)^2$$$, the total number of unit squares on the grid.

3
1 2 2 2
1 1 2 1
2 3 3 3
1 3 2 3
3 2 3 3
3 1 3 2
1 1 1 2
2 1 3 1
2 1 2 2
2 2 2 3
1 2 1 3
2 2 3 2

ABABABABAABB
1 3

4
2 4 3 4
2 1 2 2
1 3 2 3
1 3 1 4
2 2 3 2
2 2 2 3
4 1 4 2
2 1 3 1
3 1 4 1
4 3 4 4
2 3 2 4
1 1 1 2
1 2 2 2
3 1 3 2
3 2 4 2
3 4 4 4
4 2 4 3
1 1 2 1
3 3 4 3
2 3 3 3
3 2 3 3
3 3 3 4
1 2 1 3
1 4 2 4

ABABABABABABABBBABBABBBB
0 9