Problem 3 - Pousse

Description

The name of the game is "pousse" (which is French for "push"). It is a 2 person game, played on an N by N board (the original game was 4x4 but NxN is a simple generalization to adjust the difficulty of the game, and its implementation). Initially the board is empty, and the players take turns inserting one marker of their color (X or O) on the board. The color X always goes first. The columns and rows are numbered from 1 to N, starting from the top left, as in:

     1 2 3 4
    +-+-+-+-+
  1 | | | | |
    +-+-+-+-+
  2 | | | | |
    +-+-+-+-+
  3 | | | | |
    +-+-+-+-+
  4 | | | | |
    +-+-+-+-+

A marker can only be inserted on the board by sliding it onto a particular row from the left or from the right, or onto a particular column from the top or from the bottom. So there are 4*N possible "moves" (ways to insert a marker). They will be named "Li", "Ri", "Ti", "Bi" respectively, where "i" is the number of the row or column where the insertion takes place.

When a marker is inserted, there may be a marker on the square where the insertion takes place. In this case, all markers on the insertion row or column from the insertion square up to the first empty square are moved one square further to make room for the inserted marker. Note that the last marker of the row or column will be pushed off the board (and must be removed from play) if there are no empty squares on the insertion row or column.

A row or a column is a "straight" of a given color, if it contains N markers of the given color.

The game ends when an insertion creates a configuration with more straights of one color than straights of the other color; the player whose color is dominant (in number of straights) WINS.

Input

The input file of the program will contain a number N <= 100 on the first line. This will be followed by a sequence of moves (in the notation previously described) with one move per line. There are no intervening spaces or empty lines.

The program can assume that all moves in the sequence are valid.

Your job

Your job is to write a program to determine when a game has been won. The input to your program is the same as described above: an initial number followed by a sequence of moves. As soon as a move produces a winning board position, your program should print out whether ``X WINS'' or ``O WINS'', and exit. If a line containing QUIT is read before a winner is declared, your program should print out ``TIE GAME'' and exit. As a fail safe, the last line of every input file will be a QUIT line.

Program Mechanics

Thus, if your program is passed the input file prob0.dat, your program will produce the output file prob0.out.

Sample Input (1)

4
L2
T2
L2
B2
R2
QUIT

This input would result in the following configuration of the board when QUIT is reached:

     1 2 3 4
    +-+-+-+-+
  1 | |O| | |
    +-+-+-+-+
  2 |X|X| |X|
    +-+-+-+-+
  3 | | | | |
    +-+-+-+-+
  4 | |O| | |
    +-+-+-+-+

Output for Sample Input (1)

TIE GAME

Sample Input (2)

4
L2
T2
L2
B2
R2
T1
L2
QUIT

This input would result in the following configuration of the board after the second L2:

     1 2 3 4
    +-+-+-+-+
  1 |O|O| | |
    +-+-+-+-+
  2 |X|X|X|X|
    +-+-+-+-+
  3 | | | | |
    +-+-+-+-+
  4 | |O| | |
    +-+-+-+-+

Output for Sample Input (2)

X WINS