JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: $3,000 NSA Marathon Event 2 (US Only)
Problem: ChessPuzzle

Problem Statement

    ChessPuzzle is a single-player game with the following rules.



The player is given a rectangular board of cells. On each cell there are K tiles arranged in a stack, so that only the topmost tile of the stack is visible to the player. Each tile can be of one of 8 types - 1, 2, 3, 4, knight, bishop, rook and queen (denoted with '1'..'4', 'K', 'B', 'R' and 'Q', respectively).



The game is started by clicking on any cell. After the cell is clicked, the topmost tile of this cell is removed, and next tile in the stack is revealed. The cells which can be clicked next are defined with the type of the removed tile in the following way:
  • Types 1-4 allow you to click on any cell which is in the same row, column or diagonal as the previously clicked cell at distance 1-4 (where the exact distance corresponds to the type of cell clicked). Thus, type 1 allows clicking on any of 8 adjacent cells.
  • A knight "moves" exactly as the chess piece, i.e., the next cell to click is at distance 2 along one axis and 1 along the other one from the previously clicked cell.
  • The bishop, rook and queen have movement direction as the corresponding chess pieces (diagonally, vertically/horizontally and all directions respectively). They can only move to the edge of the board though. If the cell at the edge of the board is empty, the piece can not move in that direction (it doesn't stop early).
During each move the player clicks on one of the cells as defined by the tile removed on the previous move. If the last tile (the Kth) in a cell is removed, this cell can't be clicked again. If after a click there are no valid cells to be clicked,then the game ends.



The images below illustrate the available clicks for three of the pieces. The cell highlighted in red has just been clicked, containing the piece shown. The greyed out cells have already had all of their pieces removed. The cells highlighted green are those that may be clicked next.













Your code should implement two methods, as described below:
  • start(int K, String[] board). This method is called once per test case to give you the number of layers on the board K and the topmost tiles in the cells board. Each element of the board input represents one row.
  • click(String revealed). This method is called once per click. revealed gives you the type of the tile revealed with previous click; if this cell has been clicked K times, revealed will be "-" to denote this.
  • Your return from both methods should be a String formatted as "ROW COL" to denote clicking on the cell in row ROW and column COL of the board (indices are 0-based). You can return any cell from start, but you have to return a cell defined by the previously clicked tile from click.
Your score for a test case is the number of clicks done until the end of the game, divided by total number of tiles on the board. If you try to do an invalid move, the score is 0. Your overall score is the sum of your individual scores over all test cases.

Visualizer

A visualization tool is provided for offline testing. It also allows manual play.
 

Definition

    
Class:ChessPuzzle
Method:start
Parameters:int, String[]
Returns:String
Method signature:String start(int K, String[] board)
 
Method:click
Parameters:String
Returns:String
Method signature:String click(String revealed)
(be sure your methods are public)
    
 

Notes

-You can't click on a cell clicked during the previous click.
-The type of each tile is chosen uniformly and independently.
-The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). There is no explicit code size limit.
-There are 10 example test cases and 100 full submission test cases.
 

Constraints

-Board width and height will be between 6 and 15, inclusive.
-K will be between 1 and 10, inclusive.
 

Examples

0)
    
seed = 1
1)
    
seed = 2
2)
    
seed = 3
3)
    
seed = 4
4)
    
seed = 5
5)
    
seed = 6
6)
    
seed = 7
7)
    
seed = 8
8)
    
seed = 9
9)
    
seed = 10

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.