TopCoder problem "ValetParking" used in SRM 267 (Division I Level Two)



Problem Statement

    Valet parking is used to maximize the number of cars that we can park in our lot. The parking spaces are arranged in a 100 x 100 grid of squares. Each square can hold one car, and it is possible to drive a car onto any of the four orthogonally adjacent squares (provided that it is not already occupied by a car). A car may enter or leave the lot only on the corner square whose coordinates are (0,0).

The lot is full when all but one of the squares is occupied. Given the location of the one empty square and the location of the customer's car, we want to know how many times the valet will have to get into a car and drive it before he can maneuver the customer's car to the location (0,0). The valet is not allowed to drive any of the cars out of the lot.

Create a class ValetParking that contains a method minMoves that is given the coordinates (emptyRow and emptyCol) of the one empty square in the full lot, and the coordinates of the customer's car (cusRow and cusCol). The method returns the number of times the valet will have to move a car.

 

Definition

    
Class:ValetParking
Method:minMoves
Parameters:int, int, int, int
Returns:int
Method signature:int minMoves(int emptyRow, int emptyCol, int cusRow, int cusCol)
(be sure your method is public)
    
 

Constraints

-emptyRow, emptyCol, cusRow, and cusCol will be between 0 and 99, inclusive.
-(emptyRow,emptyCol) is not the same position as (cusRow,cusCol).
 

Examples

0)
    
50
22
0
0
Returns: 0
The customer's car is already at the exit position.
1)
    
0
0
1
0
Returns: 1
The valet can immediately drive the customer's car to the empty exit position.
2)
    
0
0
1
1
Returns: 5
   One way to do this is:
     a) drive a car from 1,0 to 0,0
     b) drive the customer's car from 1,1 to 1,0
     c) drive a car from 0,1 to 1,1
     d) drive a car from 0,0 to 0,1
     e) drive the customer's car from 1,0 to 0,0
3)
    
80
15
40
7
Returns: 252

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8000&pm=4679

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Math