Connection Status:
Competition Arena > ValetParking

ValetParking

SRM 267 · 2005-10-05 · by dgoodman

SRM 267 · 2005-10-05 · by dgoodman · Math
Class Name: ValetParking
Return Type: int
Method Name: minMoves
Arg Types: (int, int, int, int)
Problem Statement

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.

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)
0
9
13
0
Returns: 82
4)
99
98
99
96
Returns: 590

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

Coding Area

Language: C++17 · define a public class ValetParking with a public method int minMoves(int emptyRow, int emptyCol, int cusRow, int cusCol) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous