JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 25
Problem: AreaFiller

Problem Statement

    

Area-filler is a game played by placing colored tiles on cells of a two dimensinoal rectangular board. On each turn, you place a single tile of the color you choose onto an empty cell. After each turn, the computer will place two tiles, of randomly selected color, into unoccupied cells on the board.

You score points by placing tiles in such a way that four tiles on the board, all of the same color, form the corners of a rectangle with no tiles of any other color along the edges or interior of the rectangle. After a move is made that completes such a rectangle, the entire area is acquired, and the computer will no longer make any moves in that area.

The game is over when all spaces of the board have either been filled with a color, or acquired by completing the corners of a rectangle.

The init method will first be called, giving you basic parameters for the problem. You may return any int. Then, each call to nextMove will give you the current state of the board, where each element represents a row of the board, and each character a square within that row. A '.' represents an unoccupied square, a '*' is an already acquired square, and colored squares are given by 'A', 'B', 'C', etc. The nextMove method should return an int[] with three elements: row, column, and color, describing the next color (1-based) you wish to place, and where you wish to place it.

Your score for each test case will be the total number of squares that have been acquired. Note that the corners (or any interior squares that happen to have been the same color already) do not count as acquired. Thus, when you complete the four corners of a 3x4 rectangle, you would acquire a total of 8 squares.

Your total score will be the sum of your relative scores on each test case, where each relative score is YOURS / BEST. On any test case where you make an invalid return, or generate an error, you will score a 0.

A visualizer is available.
 

Definition

    
Class:AreaFiller
Method:nextMove
Parameters:String[]
Returns:int[]
Method signature:int[] nextMove(String[] board)
 
Method:init
Parameters:int, int, int
Returns:int
Method signature:int init(int width, int height, int colors)
(be sure your methods are public)
    
 

Notes

-Time limit is 30 seconds.
-Memory limit is 1GB.
-The first few example cases have been special crafted to facilitate testing.
-Colors are 1-based.
 

Constraints

-height and width will be chosen between 20 and 100, at random.
-colors will be chosen between 3 and 10, at random.
 

Examples

0)
    
seed = 1
10 x 10
Colors = 3
1)
    
seed = 2
20 x 20
Colors = 4
2)
    
seed = 3
40 x 40
Colors = 6
3)
    
seed = 4
70 x 70
Colors = 8
4)
    
seed = 5
100 x 100
Colors = 10
5)
    
seed = 6
77 x 71
Colors = 7
6)
    
seed = 7
28 x 80
Colors = 5
7)
    
seed = 8
35 x 24
Colors = 7
8)
    
seed = 9
44 x 84
Colors = 9
9)
    
seed = 10
33 x 87
Colors = 3

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.