APIO '11 P2 - Find the Path

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

TooDee is the name of a 2-dimensional grid-shaped land, like the well-known Cartesian coordinate system, in which cute "Dee"s live! Dees are small creatures like bees, but they are two-dimensional, and very civilized. Hives in TooDee are also different in comparison to normal beehives - they are rectangular and their edges are parallel to the geographic axes of TooDee, either exactly from east to west or from north to south.

Since Dees are extraordinarily advanced creatures, they have fixed flying paths in the world, which can be assumed to be lines joining coordinates with integer values of longitude or latitude parallel to the axes (i.e. either horizontally or vertically). The flying rules of TooDee respected by all Dees are as follows: (remember that all points in TooDee have integer longitude and latitude):

  • If you are at the point (X_S, Y_S) you can only fly to any of its 4 adjacent neighbor points (i.e. (X_S+1, Y_S), (X_S-1, Y_S), (X_S,Y_S+1), (X_S,Y_S-1).
  • You cannot enter any Deehive.
  • You can change your flying direction only when you are on an edge or corner of a Deehive.
  • You can start your flight initially in any direction you wish.

Tonight is the birthday of Deeficer (an officer of the Public Wealth Ministry of TooDee) and she wants to go home as fast as possible. Assuming she can fly with the speed of one unit of length per second, help her to find out how many seconds it would take to reach home, flying through the best path, and yet, respecting the rules!

Input Specification

The first line of input consists of a single integer, T, the number of test scenarios. It is guaranteed that 1 \leq T \leq 20. The remaining lines of input consist of these T scenarios. There is a blank line before any scenario of the input.

Each scenario begins with a line consisting of the coordinates of Deeficer's office location and her home. These two points are described by two integers X and Y. The second line of the scenario consists of a single integer N, the number of Deehives. In the remaining N lines, one Deehive is described per line. The description of a Deehive is given by the coordinates of two opposite corners of it. You can assume no two Deehives overlap or touch, even on corners. You can also assume that the home and office are distinct points. The area of each Deehive is at least one square unit.

Output Specification

For each scenario, write the number of seconds it would take for Deeficer to reach home though the shortest path, in a single line. If she is unable to reach home obeying the rules, write No Path.

Constraints

  • In all of the test cases, all coordinate are integers in the range [-10^9, 10^9] and 0 \leq N \leq 1\,000.
  • In 20\% of tests, N \leq 10 in all scenarios and all coordinates are non-negative and less than 100.
  • In 60\% of tests, all coordinates have absolute values less than 1\,000 and 0 \leq N \leq 100.

Sample Input

2

1 7 7 8
2
2 5 3 8
4 10 6 7

2 1 5 4
1
3 1 4 3

Sample Output

9
No Path

Comments

There are no comments at the moment.