TopCoder problem "GameEnding" used in SRM 271 (Division I Level Two)



Problem Statement

    

Two players play a game on a n*n chessboard. Starting with the first player, they take alternate turn putting figures on empty cells. During each turn, a player will place a figure on an empty cell in such a way that it can't be captured by any of the figures already on the board. Each figure can capture as a rook and as a knight. Rooks capture backwards, forwards, and sideways. Knights capture in an L-shape (two consecutive squares backwards, forwards, or sideways, and then one square in a perpendicular direction).

A player wins the game when the other player cannot make a move. You are given the first moves of such a game, and you are to determine who will win if both players are trying their best to win.

You are given a String[] moves representing the moves that have already been made. Each element of moves will be formatted as "xX", where x is a lowercase letter representing the vertical position and X is a number representing the horizontal position. Return one of three possible answers:

  • "First player wins", if the first player will win or has already won (there are no valid moves left, and the first player made the last move).
  • "Second player wins", if the second player will win or has already won (there are no valid moves left, and the second player made the last move).
  • "Invalid input", if the input is invalid (a figure is placed on a previously occupied square, or a figure can be captured by another figure).

 

Definition

    
Class:GameEnding
Method:result
Parameters:int, String[]
Returns:String
Method signature:String result(int n, String[] moves)
(be sure your method is public)
    
 

Notes

-The moves that are given in the input may not have been the best moves, but all subsequent moves will be the best possible moves (meaning that if there are moves leading to victory, the player must choose one of them).
 

Constraints

-n will be between 1 and 7, inclusive.
-moves will contain between 0 and n elements, inclusive.
-Each element of moves will be formatted as "xX".
-Each x is a lowercase letter between 'a' and 'a'+n-1, inclusive.
-Each X is a digit between 1 and n, inclusive.
 

Examples

0)
    
3
{"b2"}
Returns: "First player wins"
The first player makes the first move at b2. After that, only the four corner cells are available for valid moves. The second player places a figure on one of those corner cells. The first player then places a figure on the opposite corner. There are no more moves available to the second player, so the first player wins.
1)
    
4
{"a2","b3"}
Returns: "Second player wins"
Only cells c4 and d1 are available. The first player plays one of them, and the second player plays the other. The first player will then have no valid moves left, so the second player wins.
2)
    
4
{"a3","b3"}
Returns: "Invalid input"
The second player made an invalid move. The figure on b3 can be captured by the figure on a3.
3)
    
4
{"a1","b2","c3","d4"}
Returns: "Second player wins"
There are no valid moves left, and the second player made the last move, so he wins.
4)
    
7
{}
Returns: "First player wins"
5)
    
7
{"b5","g3","f2"}
Returns: "Second player wins"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8068&pm=4597

Writer:

Vedensky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Recursion