Two people are playing a game, taking turns filling in squares on a piece of graph paper.
On each turn, they can either fill in a single empty square or fill in a 2x2 block
of 4 empty squares.
Once all the squares in the grid are filled, the last player to have filled in a square is the winner.
The only restriction is that if we number the rows from top to bottom starting at zero,
the top half of every 2x2 block that a player fills in during a turn must lie in an even-numbered row.
For example, the following moves (in green) are legal:
while the following moves (in red) are illegal:
The current state of the grid will be given as a String[] state.
Each element of state will be one row of the grid,
and each character of each element of state will represent one square in the row.
A '.' (period) represents an empty square, and a '#' represents a filled-in square.
From this current state, determine who can win the game assuming both people play optimally.
If the next player to move can win return the String "first",
otherwise, return the String "second" (all quotes for clarity).
|