Connection Status:
Competition Arena > FurnitureRobbery

FurnitureRobbery

SRM 353 · 2007-06-07 · by Olexiy

SRM 353 · 2007-06-07 · by Olexiy · Dynamic Programming
Class Name: FurnitureRobbery
Return Type: int
Method Name: leastPushes
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Challenges on this problem will be temporarily unavailable.

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.

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

Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FurnitureRobbery with a public method int leastPushes(vector<string> plan) · 54 test cases · 2 s / 256 MB per case

Submitting as anonymous