P6888 [CEOI 2006] Walk

在一个陌生的大城市中找到你的目的地可能是一个挑战，尤其是如果你像 Kirk 一样是一名计算机科学家，总是试图使用最短的路径。规划可以有所帮助——给定城市的地图，Kirk 想要找到他当前位置和目的地之间的最短路径。 城市的地图可以在平面上表示为由单位方格组成的无限网格。 Kirk 目前位于方格 (0, 0)，他的目的地是方格 (X, Y)。 城市中有 N 座建筑。每座建筑是一个完全占据若干单位方格的矩形。**没有两座建筑接触或重叠**，即 Kirk 可以自由地绕过每座建筑。建筑通过指定建筑占据的两个对角方格的坐标来定义。 在每一步中，Kirk 可以走到四个相邻方格之一，但他不能踏上被建筑占据的方格。他目前的位置在城市的西入口，每个被建筑占据的方格的 x 坐标**严格大于零**。 编写一个程序，给定建筑的位置，找到从 Kirk 当前的位置到他目的地的**一条最短路径**。路径应报告为一系列垂直和水平线段，且没有两个连续的线段是平行的。路径的长度是路径中包含的方格数，不包括初始方格。

输入的第一行包含两个整数 X, Y (1 ≤ X ≤ 10^6, -10^6 ≤ Y ≤ 10^6)——目的地方格的坐标。输入的第二行包含一个整数 N (0 ≤ N ≤ 100,000)——城市中的建筑数量。接下来的 N 行中的每一行包含四个整数 X1, Y1, X2, Y2 (1 ≤ X1, X2 ≤ 10^6, -10^6 ≤ Y1, Y2 ≤ 10^6)——建筑占据的两个对角方格的坐标。

输出的第一行应包含一个整数 L——到达目的地的最短路径的长度。输出的第二行应包含一个整数 M——最短路径中的线段数量。线段数量 M 不得超过 1,000,000。 接下来的 M 行中的每一行应包含两个整数 DX 和 DY，描述 Kirk 在一个线段中的相对移动。对于每个线段，**恰好一个**值 DX 或 DY 应为零，并且没有两个连续的线段是平行的。 注意：如果有多个解决方案，你应该输出其中任何一个。

  **注意：原题还要求输出方案，本题略去。** 题面翻译由 ChatGPT-4o 提供。