TopCoder problem "Gems" used in SRM 158 (Division II Level Three)



Problem Statement

    

A very famous internet game has a board full of gems. The game is played by swapping two gems that are horizontally or vertically adjacent to make three or more gems of the same type in a vertical or horizontal line. After the move, all gems of the same type that are lined up in horizontal or vertical lines of 3 or more disappear. Then the gems above the removed gems drop down to fill the spaces, and more gems come out of the top of the board to fill the spaces created on top. A move can only be made if it causes gems to disappear.

Your job is to determine how many possible moves are left given a certain board configuration. The board will be passed in as a String[], where each character j in element i of the String[] represents the gem at row i, column j. Each gem will be represented by a capital letter 'A' - 'Z'. Each letter represents a type of gem.

If the current board configuration has no moves left, return 0. Otherwise, return the number of different moves possible. A move consists of swapping two different adjacent gems horizontally or vertically (diagonal swaps are not allowed). Two moves are different if and only if they do not involve the same two gems.

 

Definition

    
Class:Gems
Method:numMoves
Parameters:String[]
Returns:int
Method signature:int numMoves(String[] board)
(be sure your method is public)
    
 

Constraints

-board will have between 3 and 50 elements, inclusive.
-Each element of board will contain between 3 and 50 characters, inclusive.
-All elements of board will contain the same number of characters.
-Each element of board will contain only capital letters 'A'-'Z', inclusive.
-board will not have three or more similar gems in a horizontal or vertical line.
 

Examples

0)
    
{"ABC",
 "ABC",
 "BAD"}
Returns: 1

The only valid move is to swap the lower left gem with the one to its right, yielding the following board: 

ABC
ABC
ABD

Notice that two columns of 3 gems of the same type are formed.

1)
    
{"ABB",
 "BAA",
 "ABB"}
Returns: 3

The 3 valid moves are:

1. Swap the upper left gem with the gem below it.

2. Swap the middle left gem with the gem below it.

3. Swap the middle left gem with the gem to the right of it.

2)
    
{"ABA",
 "BAB",
 "ABA"}
Returns: 4

Swapping the middle gem with any of its surrounding gems results in a valid move.

3)
    
{"ABC",
 "DEF",
 "GHI"}
Returns: 0

Since no 3 gems of the same type exist, there is no way to move.

4)
    
{"SUMEEMEEPGPPG",
 "USPMIPSUSIISG",
 "UPSPGEGGPKEII",
 "KEMGISMKKIUIG",
 "MGSIIKMSISGKM",
 "SPGMSMIGMSMGM",
 "SSIIUKMPEPPUI",
 "UKUIUEMEEIGKE",
 "IPUPGUSEGSSUS",
 "EUPMKGGUKKEMI",
 "PEPSMUUEUSSIP",
 "SUMEEUSESUEKG",
 "EPSKUISGMSKGI",
 "IUGGUGGSIGUUP",
 "IUPIKKSGPPEEP",
 "KGEESGISPGGEM",
 "UEIUSSKPSSGPE",
 "KSUMKGEIMKPSE",
 "ESKEUEMMPPIGG",
 "UUIEUGGIGMEMK",
 "GPGMPPIUMEPMU",
 "IKIGGPIUEMIGS",
 "IPUSGUMKPKIPP",
 "UEEMUUEEGIPUS",
 "PPEKIKEMGGMSS",
 "EMKPMPUUMKEPU",
 "UKPGPKSUIEUPM",
 "PSUUMUKGIIPMS",
 "ESMGSKUEPGGEM",
 "SMEEIKGKGGPEG",
 "UEIEKPMESMEPP",
 "IPUIMGGMIPKMG",
 "ISSEKPKGKIUGU",
 "SSESKUGKISPUK"}
Returns: 83

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4598&pm=1767

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Simple Search, Iteration, String Manipulation