bzoj#P1368. [Baltic2004]CAR PARK

[Baltic2004]CAR PARK

题目描述

在一个 6×66 \times 6 的正方形网格中停靠着若干辆车。

其中的一号车是学校的班车,长度为 22,宽度为 11。其它车的宽度为 11,长度为 2233

每辆车的朝向是南北向或东西向。

我们可以使某辆车沿着它的朝向移动一步,前提是没有开出网格或者有别的车阻拦。

我们的目的是使一号车从网格的第三行六列右侧的出口离开,在这基础上还要使所有车移动的步数之和最小。

输入格式

第一行是车的数目 nn

此后 nn 行,第 ii 行有四个整数 li,oi,xi,yil_i,o_i,x_i,y_i

li{2,3}l_i∈\{2,3\},表示第 ii 辆车的长度。

oi{0,1}o_i ∈\{0,1\},表示第 ii 辆车的方向。若 oi=0o_i=0,表示第 ii 辆车是南北朝向;若 oi=1o_i=1,表示第 ii 辆车是东西朝向。

(xi,yi)(x_i,y_i) 表示第 ii 辆车的左上角处于网格第 yiy_i 行第 xix_i 列的位置。

输出格式

仅含一个整数,表示把班车开出网格需要的最小步数。

如果无解就输出 1-1

8
2 1 2 3
2 1 1 1
2 0 1 5
2 1 5 5
3 0 6 1
3 0 1 2
3 0 4 2
3 1 3 6
18

数据规模与约定

对于 100%100\% 的数据,n16n\leq16li{2,3}l_i\in\{2,3\}oi{0,1}o_i\in\{0,1\}1xi,yi61\leq x_i,y_i\leq6