TopCoder problem "FurnitureRobbery" used in SRM 353 (Division I Level Three)



Problem Statement

    

Two robbers break into an antique shop and decide to steal an old famous sofa. The shop is quite messy, so this may be a difficult task.

You are given the floorplan of the shop in the String[] plan, with the first element of plan corresponding to the top row of the floorplan. Each piece of furniture is labeled with a distinct uppercase letter ('A'-'Z'). The famous sofa is labeled with 'A'. Empty cells are marked with '.'. You can push any of the pieces of furniture in any of the four directions (right, up, left and down) one cell at a time as long as it doesn't collide with any other furniture or with walls.

Your objective is to move the famous sofa so that at least one of its cells is in the top row.

Return the least number of pushes required to accomplish this goal, or -1 if it is not possible.

 

Definition

    
Class:FurnitureRobbery
Method:leastPushes
Parameters:String[]
Returns:int
Method signature:int leastPushes(String[] plan)
(be sure your method is public)
    
 

Constraints

-plan will contain between 2 and 5 elements, inclusive.
-All elements in plan will have the same length.
-Each element in plan will contain between 2 and 6 characters, inclusive.
-Each character in plan will be an uppercase letter ('A'-'Z') or '.'.
-Each piece of furniture will occupy at least 2 cells.
-Cells with same letters will be connected.
-There will be exactly one 'A' piece.
 

Examples

0)
    
{"......",
 ".BBB.X",
 ".B.B.X",
 "DDCC.Y",
 "..AAAY"}
Returns: 13
......         ......         BBB...         BBB...         BBB...         BBB...         BBBAAA
.BBB.X         .BBB.X         B.B..X         B.B..X         B.B..X         B.B...         B.B...
.B.B.X 3 moves .B.B.X 2 moves .....X 2 moves ..AAAX 1 move  ..AAAX 2 moves ..AAA. 3 moves ......
DDCC.Y ------> CC...Y ------> CC...Y ------> CC...Y ------> CC..Y. ------> CC..YX ------> CC..YX
..AAAY         DDAAAY         DDAAAY         DD...Y         DD..Y.         DD..YX         DD..YX
13 pushes total.
1)
    
{"......",
 ".BBB.X",
 ".B.B.X",
 "....YY",
 "..AAAY"}
Returns: 11
2)
    
{"...C.C",
 "BBBCCC",
 "B.B...",
 ".XX..Y",
 "..AAAY"}
Returns: 13
3)
    
{"......",
 "ZBBBXY",
 "ZBBBXY",
 "EAAACC",
 "E.DDCC"}
Returns: 20
4)
    
{"......",
 "BBB...",
 "BCBC..",
 ".CCC.Y",
 "..AAAY"}
Returns: 16
5)
    
{".C",
 "BC",
 "BC",
 "B.",
 "AA"}
Returns: -1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10710&pm=7843

Writer:

xOberon

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Dynamic Programming