P3716 [CTSC2000] Icefield Exploration

Legend says there is a vast icefield in Antarctica, under which lie ruins of a prehistoric civilization. The entire icefield is divided into many equal-sized grid cells. On this icefield there are $N$ rectangular icebergs of different sizes, each as ancient as Antarctica itself. Each rectangular iceberg occupies at least one cell and always fully occupies cells. Icebergs neither overlap nor touch each other at edges or points. The following two cases cannot occur:  After years of preparation, the $\text{ACM}$ exploration team decided to search for the ruins on this icefield. According to their information, there is a one-cell-deep pit on the icefield that hides a switch made by prehistoric humans. The only thing that can activate this switch is a movable small ice block that is almost one cell in size. Obviously, such a small independent ice block could not naturally exist in Antarctica, so it must also be a product of the prehistoric civilization. They want to push this block into the pit to open a passage to the bottom of the icefield and excavate the secrets of the prehistoric civilization. Neither the starting position of the ice block nor the position of the deep pit is adjacent to any iceberg. Both the ice surface and the icebergs are perfectly smooth. A gentle push makes the ice block slide forward until it hits an iceberg and stops next to its side. The ice block can slide through any area of the ice surface without icebergs and can pass between two icebergs (see the figure below). The ice block can only be pushed along the grid directions.  Please help them push the ice block into the deep pit with the minimum number of pushes.

The first line contains the number of icebergs $N$. The second line contains the coordinates of the starting cell of the ice block, $X_{1}, Y_{1}$. The third line contains the coordinates of the deep pit, $X_{2}, Y_{2}$. Each of the next $N$ lines contains four integers, the coordinates of the upper-left and lower-right cells of an iceberg, $X_{i_{1}}, Y_{i_{1}}, X_{i_{2}}, Y_{i_{2}}$.

Output a single integer: the minimum number of pushes. If it is impossible to push the ice block into the deep pit, output 0.

$1 \leq N \leq 4000$. Sample explanation: The moving plan is shown in the figure.  Translated by ChatGPT 5