TopCoder problem "DominoesFalling" used in TCCC06 Round 2C (Division I Level Three)



Problem Statement

    

This problem contains an image that can be viewed in the applet.

The domino effect is a chain reaction triggered by a single tile falling down. The tile falls into another tile, which falls into the next tile, and so on (see picture below).

Consider an infinite line of cells, some of which are occupied by tiles. We want to arrange the tiles in such a way that pushing the leftmost tile will lead to all the tiles falling down. A tile will push down a neighboring tile to its right if there are between 1 and 4 free cells, inclusive, between them.

You will be given a String[] cells. Concatenate the elements of cells to create a single string representing a segment of the infinite line. Tiles are represented by 'X' characters and free cells are represented by '.' characters. All cells to the left and right of the given segment are free. You may only move tiles into free cells. Return the minimal number of tiles you must move to achieve the desired domino effect.

 

Definition

    
Class:DominoesFalling
Method:rearrangeTiles
Parameters:String[]
Returns:int
Method signature:int rearrangeTiles(String[] cells)
(be sure your method is public)
    
 

Constraints

-cells will contain between 1 and 50 elements, inclusive.
-Each element of cells will contain between 1 and 50 characters, inclusive.
-Each element of cells will contain only '.' and uppercase 'X' characters.
-cells will contain at least two 'X' characters.
 

Examples

0)
    
{"XX"}
Returns: 1
The tiles are too close. So, we need to move one them.
1)
    
{"X.....X"}
Returns: 1
The tiles are too far apart. So, we need to move one them.
2)
    
{"X.X............",
 "...............",
 ".....X.X.X.....",
 "...............",
 "............X.X"}
Returns: 4
3)
    
{"X.X....X..X...", ".X......"}

Returns: 0
4)
    
{".XX.X.XXXXXX", "X.X.XXXXXXXXXXXX", ".X.X.X.XXXXXXX.XXX", ".XXXXXX.XX", 
 "XX.XXXXX.XXXXX", "XXXXX...X...X", "XXXX.XXXXXXXXX.XXXXX"}
Returns: 34
5)
    
{".......X.X.", ".....X.....", ".............X", "....X...X..", ".X...X.X..", 
 ".XXX........X......X", "......X..X....", "....X..........."}
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10113&pm=6762

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

Problem categories:

Dynamic Programming