Solution

The framing of the problem means that it is most likely a Dijkstra problem; the hardest part is designing the nodes and edges.

To form the edges, we look at the possible movements that we can take. Firstly, we can jump off of the current rectangle and potentially reach a new rectangle. Secondly, we can move along our current rectangle.

In this case, every point on the border of a Deehive is a vertex, and edges connect adjacent points on Deehives as well as jumps between Deehives. However, this would be too many (up to $10^9$) vertices and edges!

To optimize, we can use coordinate compression. Consider the set of significant lattices lines: those passing through corners (and edges) of Deehives, the start point, or end point. Let significant lattice points be all intersections of these lines.

It can be shown that any path (between two significant lattice points) through TooDee can be transformed to use only significant lattice lines without increasing the length of the path.

Build the graph along the significant lattice grid and run Dijkstra's algorithm to find the shortest path.

Implementation

Time complexity: $\mathcal{O}(N^2 \log N)$

Copy
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Rect {
	int x1, y1, x2, y2;
	Rect(int a = 0, int b = 0, int c = 0, int d = 0) : x1(a), y1(b), x2(c), y2(d) {
		if (x1 > x2) swap(x1, x2);
		if (y1 > y2) swap(y1, y2);