Car Park
Time limit1sMemory limit512 MB
A 6x6 parking lot holds 2x1 and 3x1 cars that slide only along their long axis; find the fewest single-square moves to drive car 1 out the row-3 exit, or -1 if impossible.
- Level
Hard8 of 10
- Topics
- BFS, Simulation, Implementation, Hash map
- Solved
- No attempts yet
Problem
The youth hostel where BOI2004 is being held has a parking lot made up of a 6 by 6 grid of squares. The rows of the lot are numbered 1 to 6 from top to bottom, and the columns are numbered the same way from left to right. There is only one exit from the lot, on the right side of row 3.
There are N parked cars in the lot. Your car is among them, but it has no easy way out because the other cars block it. You and your friends can move the cars forwards and backwards, since the gearbox of every car is in neutral. You may not steer or turn, neither your own car nor any of the other cars.
Your task is to determine the minimum number of steps needed to get your car, which is 2x1 squares in size, off the parking lot. One step means moving one car one square. None of the other cars may be moved off the lot.
There are only two types of cars. One type is 2x1 squares in size, and the other occupies 3x1 squares. Cars may only be moved along the longer of their two axes.
In the given example N = 8 and your car is labeled with the number 1.
Below is the minimum sequence of length 18 to exit the lot with your car: 4←←←, 2→, 6↑, 3↑, 8←←, 5↓↓↓, 7↓↓, 1→→→→→.
Input
The first line of the input contains the number of cars N (1 ≤ N ≤ 16).
Each of the following N lines contains the description of the car labeled with the number i. Each line consists of four integers specifying the length li, the orientation oi, and the start (upper left) coordinates xi (column number) and yi (row number). Neighboring numbers are separated by a single space character. oi = 1 means the car is parked horizontally.
Otherwise it is parked vertically. The following limits apply: li ∈ {2, 3}, oi ∈ {0, 1}, 1 ≤ xi, yi ≤ 6.
Your car is described in the line right after the line containing N (that is, the second line of the input file). Your car has to exit the lot through the only exit.
Output
The output must consist of a single integer, the minimum number of steps needed to exit the lot in your car.
If it is impossible to exit the lot, print -1.