TopCoder problem "ParkingLot" used in SRM 168 (Division I Level Three)



Problem Statement

    

You are in a parking lot trying to find a spot to park. In this parking lot, each car knows about every spot on the map, and about all the other cars' locations. Since you can drive faster than you can walk, it's not always best to park at a spot which is closest to your car, but spots that are available close to the store may be taken by other cars before you can get there, or may take longer to get to than it does to walk from another spot. In any case, you need to find the best spot to park at so you can get to the store the fastest.

The parking lot will be presented to you as a grid of characters in a String[] lot. Each character represents the initial contents of each position in the grid. The characters are defined as:

'.' = open street

'X' = obstacles

'A' = available parking spots

'U' = used parking spots

'E' = the store entrance

'Y' = your car

'C' = other cars

While driving or walking, one can only travel to horizontally or vertically adjacent squares. Every car obeys the speed limit, and it takes 1 second to drive from one square to an adjacent one. However it takes you 2 seconds to walk to an adjacent square. All cars can drive freely on squares that contain other moving cars, or just have empty streets, but they cannot drive through a square that contains a parked car, an obstacle, or the entrance of the store. In addition, once a car enters a parking space, it must park. No car can drive out of a parking space once it drives into it. On foot you can walk on empty street or empty parking spots, through squares which have parked cars (assume the parked cars left enough space to walk through), moving cars (pedestrians have the right of way), and into the entrance of the store, but you still cannot pass through obstacles. Assume that there are no people on foot while you are driving.

When choosing a space to park, the other cars will always drive to the closest spot that they know they can park at. If two or more such spots exist, then the car will prefer spots that are in lower indexes of lot. If two or more spots are in the same index of lot the car will prefer spots that come earlier in the String.

We shall give each car in the map (including yours) a number based on its starting position. If a car's starting position is in character i in element j of lot, assign that car the number 100 * j + i. So if a car is at character 5 in the 10th element of lot it would get number 1005. Note that both i and j are 0-based indexes.

If two or more cars can get to a space at the same time and wish to park there, the car with the lowest assigned number will get first choice at the spot. This does not mean that the lowest numbered car will take the spot, because it may have other spots to consider. However, all the cars know which spots all the other cars will take (including yours), so they will only drive to spots they know they will get.

You have a slightly different strategy than the other cars. Since your ultimate goal is to get to the store the fastest, and not into just any parking spot the fastest, you want to consider how long it will take to walk to the store after parking. Therefore, you may pass up spots which are closer to your starting position in order to get a spot which is closer to the store.

If all the available spaces will fill up before you can get to them, or you cannot get to the store entrance, return -1. Otherwise, return the time it takes you to get to the store entrance in seconds.

 

Definition

    
Class:ParkingLot
Method:fastest
Parameters:String[]
Returns:int
Method signature:int fastest(String[] lot)
(be sure your method is public)
    
 

Constraints

-lot will have between 1 and 50 elements, inclusive.
-Each element of lot will have between 1 and 50 characters, inclusive.
-Each element of lot will have the same number of characters.
-Each character in lot will be one of '.', 'X', 'A', 'U', 'E', 'Y', or 'C'.
-There will be at most 50 'C' characters in lot
-There will be exactly one 'E' character in lot
-There will be exactly one 'Y' character in lot
 

Examples

0)
    
{".Y...........C",
 ".XUUUUUUUAUUX.",
 ".XUUUAUUAUUUX.",
 "..C...........",
 ".XUUUUUUAUUUX.",
 ".XUUUUUUUUUAX.",
 "......C.......",
 ".............E"}
Returns: 29
This is a typical parking lot situation. There is a nice close parking spot to the entrance, but unfortunately, the bottom-most car takes that spot. Assume a coordinate system where (X,Y) is the Xth column of the Yth row in lot. The upper right car takes the spot at (9,1), and the middle car takes the spot at (5,2). This leaves spots at (8,2) and at (8,4). Both spots can be attained in 13 seconds, but the one at (8,4) is closest to the entrance. Note that you can travel through the used parking spots once on foot.
1)
    
{"C..A..Y.E"}
Returns: -1
A conflict occurs, and you do not get the spot. Since no other spots exist, it is impossible to get to the entrance.
2)
    
{"C..A.Y..E"}
Returns: 12
Here, you can get to the spot one second before the other car. Therefore, you get the spot even though the other car's assigned number is lower.
3)
    
{"Y...C",
 ".XXX.",
 ".....",
 "UUAUU",
 "EA..."}
Returns: 11
You cannot drive through a parking spot to get to another one.
4)
    
{".X.U..X....UU.U.XA...UC..U.UA.A.E.A",
 "..U..A.X...XX...U...U...X..U.XUX.X.",
 "U...U.X...U..........A...AXU.U..UUC",
 "UX..XX.AU..XAA.X.U.XCX..UX.......U.",
 "UAUX..UX...X....X.X..C.X..U...AXU..",
 "AA..AA..XUAX..A..XXX..AUUXUAXU.XUAU",
 "..A....A...XUU..A..A.XU..U..A.XX.X.",
 "XX.XU...AX.A.A.....UAA.UX.XA.C....X",
 ".UA.X.A.C...A..UXA.UAX.U.CU.XU....X",
 "..XX....UUU...XX..U..A.......U..A..",
 ".ACCUU.A.A.A.XX.....X..UX..A..U..X.",
 "XCX..UX...X.A.XAUA.UX.X.UA..U..A.A.",
 "UA..X.UC...U..X.AUUAX.U.X.......UA.",
 "..X.XXX..AXX.U..XXU..X...A...UAXX..",
 ".U.A..A.XX....XC.XAUX..AXUX......A.",
 "...X.A..AX.UU.XU......A.........AA.",
 "...UXU..X...U..U.U.X.U...U......UX.",
 "A.U.UA...CA....X..UXUA..X..XX..U...",
 "XXUC.CAU..X.U.......A...U..X.....XA",
 "..XA...U...UXYC.CAU...UXA..A...A...",
 "...XA....U.A.A...CX...A...AX..U..AC",
 "U..X.AX..U..UXX............AA..A..."}
Returns: 52

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4645&pm=1678

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Search