UVA393 The Doors

题目描述

你被关在了一个长和宽都是 $10$ 的正方形房间里,以这个房间的左下角为原点建立坐标轴,房间的四个角的坐标分别为 $(0,0)$,$(0,10)$,$(10,0)$,$(10,10)$ 。 你正处于房间 $(0,5)$ 的位置,而出口在 $(10,5)$ 。 房间中还有 $n$ 堵平行于 $y$ 轴的墙$(0\le n\le 18)$,每堵墙都有两个缺口,只有缺口处才能够穿过。 现在给出墙的个数 $n$ ,每堵墙的 $x$ 坐标,以及每堵墙的两个缺口端点的 $y$ 坐标,求出到达出口的最短路径。 ![](https://cdn.luogu.com.cn/upload/image_hosting/sbqo6f0g.png)

输入格式

输出格式