P7182 [BalticOI 2004] Car Park (Day2)

The youth hostel that hosted BOI 2004 has a car park made up of a $6\times 6$ grid. Rows are numbered consecutively from $1$ to $6$ from top to bottom; columns are numbered in the same way from left to right. There is only one exit, located at row $3$, column $6$. There are $n$ cars parked in the car park. Your car is among them, but unfortunately, since your car is blocked by another car, it cannot leave directly. You and your friends can move the cars. However, neither your car nor any other car is allowed to turn or rotate. You need to determine the minimum number of moves required to make your $2\times 1$ car (numbered $1$) leave the car park. One move means moving one car by one grid cell. No other car may leave the car park. There are only two types of cars: $2\times 1$ cars and $3\times 1$ cars. A car can only move along the axis parallel to its longer side.

The first line contains an integer $n$. The next $n$ lines each contain four integers $l,opt,x,y$, representing the car length, the parking orientation (vertical is `0`, horizontal is `1`), and the coordinates of the car’s top-left cell.

Output one integer on a single line, the minimum number of moves needed to make the car leave the car park. If it is impossible to make the car leave, output `-1`.

#### Sample 1 Explanation  Steps (car number $+$ move sequence): - $4\gets\gets\gets$; - $2\to$; - $6\uparrow$; - $3\uparrow$; - $8\gets\gets$; - $5\downarrow\downarrow\downarrow$; - $7\downarrow\downarrow$; - $1\to\to\to\to\to$. #### Constraints For $100\%$ of the testdata, $1\le n\le 16$, $opt\in\{0,1\}$, $l\in\{2,3\}$, $1\le x,y\le 6$. #### Notes Translated from [BalticOI 2004 Day2 C Car Park](https://boi.cses.fi/files/boi2004_day2.pdf). Translated by ChatGPT 5