P3632 [APIO2011] Pathfinding

TooDee is a two-dimensional grid-like land (just like the well-known Cartesian coordinate system), home to many adorable Dees. Dees are small bee-like creatures that move only in 2D, and they are very civilized and advanced. The hives in TooDee are quite different from those in the ordinary world: they are rectangles whose sides are parallel to TooDee’s geographic coordinate axes, meaning each rectangle’s sides run either east–west or north–south. Because Dees are advanced beings, they have many fixed flight corridors. These corridors are composed of axis-parallel line segments, and line segments intersect only at points whose coordinates are integers. When a Dee flies in TooDee, it must follow the rules below (remember that in TooDee all points have integer coordinates): 1. If currently at point $(X, Y)$, the next step may go only to one of the four neighboring points $(X, Y - 1), (X, Y + 1), (X - 1, Y), (X + 1, Y)$. 2. Entering a hive is not allowed. 3. A change of direction is allowed only at a hive’s corners or along its edges. 4. At the start, one may fly in any direction. Tonight is the birthday of the daughter of the Minister of Public Finance, Deeficer. She wants to get home as soon as possible. Please help her find the fastest route home. Assume she can fly a distance of 1 unit per second.

Each test file contains multiple test cases. The first line contains an integer $T$, the number of test cases. Then the $T$ test cases follow, with a blank line separating consecutive cases. There are at most $20$ test cases. For each test case, the first line contains four integers $x_s, y_s, x_t, y_t$, meaning the coordinates of Deeficer’s office and home are $(x_s, y_s)$ and $(x_t, y_t)$, respectively. The second line contains an integer $n$, the number of hives. The next $n$ lines describe all hives; on the $i$-th of these lines there are four integers $x_{i_1}, y_{i_1}, x_{i_2}, y_{i_2}$, giving the coordinates of two opposite corners of the $i$-th hive as $(x_{i_1}, y_{i_1})$ and $(x_{i_2}, y_{i_2})$. No two hives intersect or touch (not even at a corner). The office and home are at different locations. Each hive has positive area.

For each test case, output one integer: the minimum time (in seconds) for Deeficer to get home. If she cannot get home under the rules, output `No Path`.

For $20\%$ of the testdata, $n\leq 10$, and all coordinates are non-negative integers less than $100$. For $60\%$ of the testdata, $n\leq 100$, and the absolute value of every coordinate is less than $10^3$. For $100\%$ of the testdata, $0\leq n\leq 10^3$, and the absolute value of every coordinate is at most $10^9$. Translated by ChatGPT 5