1. Идея

Нужно попасть из клетки ((x_0, y_0)) в клетку ((x_1, y_1)) на бесконечной шахматной доске, но ходить можно только по разрешённым клеткам. Разрешённые клетки заданы не поштучно, а отрезками по строкам: для строки (r) разрешены все клетки с колонками от (a) до (b).

Разрешены 8 направлений движения, то есть из клетки можно перейти в любую соседнюю по стороне или по диагонали клетку.

Так как каждый ход имеет одинаковую цену (1), задача сводится к поиску кратчайшего пути в неявном графе. Естественный способ — поиск в ширину (BFS).

Главная трудность не в самом BFS, а в том, что координаты могут быть очень большими, и вся доска бесконечная. Поэтому нельзя строить массив поля. Нужно хранить только те клетки, которые реально разрешены.

2. Наблюдения

Наблюдение 1. Количество разрешённых клеток ограничено

Хотя координаты могут быть до (10^9), число строк-отрезков невелико, и суммарное число разрешённых клеток по условию ограничено разумной величиной. Значит, можно явно перечислить все разрешённые клетки и хранить их в set / unordered_set.

То есть для каждого описания ((r, a, b)) добавим клетки:

[ (r, a), (r, a+1), \dots, (r, b) ]

Наблюдение 2. Граф неявный, но соседей у вершины всего 8

Из клетки ((x, y)) можно перейти только в одну из 8 клеток:

[ (x+dx, y+dy), \quad dx,dy \in {-1,0,1}, \quad (dx,dy)\ne(0,0) ]

Значит, при BFS достаточно для каждой текущей клетки проверить 8 соседей.

Наблюдение 3. Посещённые клетки удобно удалять из множества разрешённых

Можно хранить все ещё не посещённые разрешённые клетки в множестве. Тогда, когда мы впервые попадаем в клетку, сразу удаляем её из множества.

Это удобно:

• не нужен отдельный visited;
• проверка можно ли туда идти и не были ли там раньше сводится к одной операции: есть ли клетка в множестве.

Наблюдение 4. Если старт или финиш не разрешены, ответа нет

Даже BFS запускать бессмысленно, если хотя бы одна из этих клеток отсутствует среди разрешённых.

3. Алгоритм

1. Считываем старт ((x_0, y_0)) и финиш ((x_1, y_1)).
2. Считываем (n) строк с описаниями разрешённых клеток.
3. Для каждого отрезка ((r, a, b)) добавляем все клетки ((r, c)), где (a \le c \le b), в множество разрешённых клеток.
4. Проверяем, что старт и финиш принадлежат этому множеству. Если нет — выводим -1.
5. Запускаем BFS:
   • очередь хранит клетки и расстояние до них;
   • стартовую клетку помещаем в очередь и удаляем из множества разрешённых;
   • пока очередь не пуста:
     • извлекаем клетку;
     • если это финиш, выводим расстояние;
     • перебираем 8 соседей;
     • если сосед есть в множестве разрешённых, удаляем его оттуда и кладём в очередь с расстоянием на 1 больше.
6. Если BFS закончился, а финиш не найден, выводим -1.

4. Почему это работает

Докажем корректность алгоритма.

1. BFS рассматривает ровно допустимые пути

В очередь попадают только клетки, которые:

• разрешены по условию;
• соседствуют с уже достигнутой клеткой;
• ещё не были посещены.

Значит, любой путь, который строит BFS, состоит только из разрешённых клеток и использует только допустимые ходы. Следовательно, все найденные BFS маршруты корректны.

2. Если существует путь, BFS обязательно найдёт финиш

Рассмотрим любую разрешённую клетку, достижимую из старта.
Из старта BFS начинает обход, а затем переходит во все разрешённые соседние клетки, потом в соседей соседей и так далее. Это обычный обход графа в ширину по всем вершинам связной компоненты старта.

Значит, если финиш достижим, он обязательно будет когда-то помещён в очередь и обработан.

3. Первый найденный путь — кратчайший

Все рёбра графа имеют одинаковый вес (1). BFS обходит вершины по неубыванию расстояния от старта:

• сначала все клетки на расстоянии (0),
• потом на расстоянии (1),
• потом на расстоянии (2),
• и так далее.

Поэтому в момент, когда финиш впервые извлекается из очереди, расстояние до него минимально возможное.

Следовательно, алгоритм выводит длину кратчайшего пути, а если пути нет — -1.

5. Сложность

Пусть (K) — суммарное число разрешённых клеток.

• Построение множества разрешённых клеток: (O(K)) вставок.
• BFS обрабатывает каждую разрешённую клетку не более одного раза.
• Для каждой обработанной клетки проверяется 8 соседей.

Итого:

• время: (O(K)) в среднем при использовании хеш-таблицы;
• память: (O(K)).

IDEA

Даны начало и конец пути на клетчатой плоскости и список разрешённых клеток по строкам. Ходить можно в любую из 8 соседних клеток, но только по разрешённым клеткам. Координаты велики, поэтому всю плоскость хранить нельзя, однако разрешённых клеток не более нескольких десятков тысяч.

Сохраним все разрешённые клетки в хеш-таблице. Затем запустим обычный BFS от стартовой клетки по графу разрешённых клеток: из каждой клетки пробуем 8 направлений, и если сосед разрешён и ещё не посещён, добавляем его в очередь. Так как все рёбра имеют одинаковый вес 1, BFS найдёт кратчайшее расстояние. Если конечная клетка не достигнута, ответ -1.

Корректность:

• граф состоит ровно из разрешённых клеток, между двумя клетками есть ребро тогда и только тогда, когда они соседние по одному из 8 направлений;
• любой допустимый путь в задаче — это путь в этом графе, и наоборот;
• BFS в невзвешенном графе всегда находит кратчайшее число рёбер от старта до всех достижимых вершин;
• значит, найденное расстояние до финиша равно минимальному числу ходов, а если вершина недостижима, ответа нет и нужен -1.

COMPLEXITY

Пусть K — число разрешённых клеток. Тогда:

• время: O(K), так как каждая разрешённая посещённая клетка обрабатывается не более одного раза, для неё проверяются 8 соседей;
• память: O(K) на хранение разрешённых клеток, очереди и множества посещённых.

CPP

#include <bits/stdc++.h>
using namespace std;

struct PairHash {
    size_t operator()(const pair<int,int>& p) const noexcept {
        return (static_cast<uint64_t>(static_cast<uint32_t>(p.first)) << 32) ^
               static_cast<uint32_t>(p.second);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int x0, y0, x1, y1;
    cin >> x0 >> y0 >> x1 >> y1;

    int n;
    cin >> n;

    unordered_set<pair<int,int>, PairHash> allowed;
    allowed.reserve(200000);

    for (int i = 0; i < n; ++i) {
        int r, a, b;
        cin >> r >> a >> b;
        for (int c = a; c <= b; ++c) {
            allowed.insert({r, c});
        }
    }

    pair<int,int> start = {x0, y0};
    pair<int,int> finish = {x1, y1};

    if (!allowed.count(start) || !allowed.count(finish)) {
        cout << -1 << '\n';
        return 0;
    }

    unordered_map<pair<int,int>, int, PairHash> dist;
    dist.reserve(200000);
    queue<pair<int,int>> q;

    dist[start] = 0;
    q.push(start);

    const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();

        if (cur == finish) {
            cout << dist[cur] << '\n';
            return 0;
        }

        int x = cur.first;
        int y = cur.second;

        for (int dir = 0; dir < 8; ++dir) {
            pair<int,int> nxt = {x + dx[dir], y + dy[dir]};
            if (allowed.count(nxt) && !dist.count(nxt)) {
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}

PYTHON

from collections import deque
import sys

def main():
    input = sys.stdin.readline

    x0, y0, x1, y1 = map(int, input().split())
    n = int(input())

    allowed = set()
    for _ in range(n):
        r, a, b = map(int, input().split())
        for c in range(a, b + 1):
            allowed.add((r, c))

    start = (x0, y0)
    finish = (x1, y1)

    if start not in allowed or finish not in allowed:
        print(-1)
        return

    q = deque([start])
    dist = {start: 0}

    dirs = [(-1, -1), (-1, 0), (-1, 1),
            (0, -1),           (0, 1),
            (1, -1),  (1, 0),  (1, 1)]

    while q:
        x, y = q.popleft()
        if (x, y) == finish:
            print(dist[(x, y)])
            return

        nd = dist[(x, y)] + 1
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            nxt = (nx, ny)
            if nxt in allowed and nxt not in dist:
                dist[nxt] = nd
                q.append(nxt)

    print(-1)

if __name__ == "__main__":
    main()