TopCoder problem "GridGame" used in TCO05 Qual 1/3 (Division I Level Three)



Problem Statement

    In a simple game, two players take turns placing 'X's in a 4x4 grid. Players may place 'X's in any available location ('.' in the input) that is not horizontally or vertically adjacent to another 'X'. The player who places the last 'X' wins the game. It is your turn and you want to know how many of the moves you could make guarantee you will win the game, assuming you play perfectly.
 

Definition

    
Class:GridGame
Method:winningMoves
Parameters:String[]
Returns:int
Method signature:int winningMoves(String[] grid)
(be sure your method is public)
    
 

Constraints

-grid will contain exactly 4 elements.
-Each element of grid will contain 4 characters ('X's or '.'s), inclusive.
-There will be no two horizontally or vertically adjacent 'X's in grid.
 

Examples

0)
    
{"....",
 "....",
 "....",
 "...."}
Returns: 0
You can't win this game.
1)
    
{"....",
 "....",
 ".X..",
 "...."}
Returns: 11
Any legal move guarantees you win the game.
2)
    
{".X.X",
 "..X.",
 ".X..",
 "...."}
Returns: 1
3)
    
{".X.X",
 "..X.",
 "X..X",
 "..X."}
Returns: 0
4)
    
{"X..X",
 "..X.",
 ".X..",
 "X..X"}
Returns: 0
There are no valid moves.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4712

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8020&pm=4712

Writer:

lars2520

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Recursion