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

Constraints

Examples