bzoj#P1368. [Baltic2004]CAR PARK
[Baltic2004]CAR PARK
题目描述
在一个 的正方形网格中停靠着若干辆车。
其中的一号车是学校的班车,长度为 ,宽度为 。其它车的宽度为 ,长度为 或 。
每辆车的朝向是南北向或东西向。
我们可以使某辆车沿着它的朝向移动一步,前提是没有开出网格或者有别的车阻拦。
我们的目的是使一号车从网格的第三行六列右侧的出口离开,在这基础上还要使所有车移动的步数之和最小。
输入格式
第一行是车的数目 。
此后 行,第 行有四个整数 。
,表示第 辆车的长度。
,表示第 辆车的方向。若 ,表示第 辆车是南北朝向;若 ,表示第 辆车是东西朝向。
表示第 辆车的左上角处于网格第 行第 列的位置。
输出格式
仅含一个整数,表示把班车开出网格需要的最小步数。
如果无解就输出 。
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
数据规模与约定
对于 的数据,,,,。