Путь королевского гонца

1. Идея

Нужно найти минимальное число ходов на клетчатой плоскости, где ходить можно в 8 направлений, но только по разрешённым клеткам.

Это классическая задача на поиск кратчайшего пути в невзвешенном графе:

• каждая разрешённая клетка — вершина графа;
• между двумя вершинами есть ребро, если клетки соседние по стороне или по углу;
• требуется найти кратчайшее расстояние от старта до финиша.

Для таких задач лучше всего подходит BFS — поиск в ширину.

Главная особенность задачи: карта бесконечная, координаты большие, но суммарное число разрешённых клеток не превышает 10^5. Значит, нельзя строить всю карту, нужно хранить только разрешённые клетки.

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

Наблюдение 1. Координаты большие, но важных клеток мало

Хотя r и c могут быть до 10^9, реально доступны только клетки, перечисленные в отрезках дорог.

Поэтому достаточно хранить множество всех разрешённых клеток.

Наблюдение 2. Из каждой клетки есть не более 8 переходов

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

• (x-1, y-1)
• (x-1, y)
• (x-1, y+1)
• (x, y-1)
• (x, y+1)
• (x+1, y-1)
• (x+1, y)
• (x+1, y+1)

Но переход возможен только если соседняя клетка разрешена.

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

Вместо отдельного массива visited можно использовать такой приём:

• все ещё не посещённые разрешённые клетки лежат в множестве allowed;
• как только клетка попадает в очередь BFS, удаляем её из allowed.

Тогда:

• проверка "можно ли сюда пойти?" делается через поиск в множестве;
• повторно одна и та же клетка в очередь не попадёт.

Наблюдение 4. Почему BFS даёт минимум

Все ходы имеют одинаковую цену: один переход стоит 1.

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

3. Алгоритм

1. Считываем старт (x0, y0) и финиш (x1, y1).
2. Считываем n отрезков дорог.
3. Для каждого отрезка (r, a, b) добавляем в множество allowed все клетки:
   • (r, a)
   • (r, a+1)
   • ...
   • (r, b)
4. Проверяем, что старт и финиш действительно есть в allowed.
   • Если какой-то из них отсутствует, выводим -1.
5. Запускаем BFS:
   • кладём старт в очередь с расстоянием 0;
   • удаляем старт из allowed.
6. Пока очередь не пуста:
   • достаём текущую клетку и её расстояние;
   • если это финиш, выводим расстояние;
   • перебираем 8 соседей;
   • если сосед есть в allowed, удаляем его оттуда и добавляем в очередь с расстоянием dist + 1.
7. Если очередь закончилась, а финиш не найден, выводим -1.

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

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

1. Граф построен правильно

Мы рассматриваем только разрешённые клетки. Для каждой такой клетки возможны переходы только в 8 соседних клеток. Это в точности совпадает с условием задачи.

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

2. Каждая клетка посещается не более одного раза

Как только клетка впервые найдена и добавлена в очередь, мы сразу удаляем её из множества allowed.

Поэтому:

• второй раз та же клетка уже не будет считаться доступной;
• в очередь она повторно не попадёт.

Значит, каждая разрешённая клетка обрабатывается не более одного раза.

3. BFS находит кратчайшее расстояние

BFS работает слоями:

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

Когда клетка впервые извлекается из очереди, найденное расстояние до неё минимально.

Следовательно, когда мы впервые достигаем клетки (x1, y1), число шагов минимально среди всех возможных путей.

4. Если путь существует, он будет найден

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

Если финиш достижим, он обязательно окажется среди них, и алгоритм до него дойдёт.

Если финиш не достижим, BFS завершится после обхода всей достижимой компоненты, и мы корректно выведем -1.

Итак, алгоритм всегда выводит правильный ответ.

5. Сложность

Пусть K — суммарное количество разрешённых клеток. По условию K <= 10^5.

Построение множества

Для всех отрезков мы добавляем все разрешённые клетки в множество.

Это занимает O(K).

BFS

Каждая клетка:

• не более одного раза попадает в очередь;
• для неё проверяются 8 соседей.

Значит, BFS работает за O(K).

Итоговая сложность

• Время: O(K)
• Память: O(K)

6. Код на C++17

#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> target = {x1, y1};

    if (allowed.find(start) == allowed.end() || allowed.find(target) == allowed.end()) {
        cout << -1 << '\n';
        return 0;
    }

    queue<pair<pair<int, int>, int>> q;
    q.push({start, 0});
    allowed.erase(start);

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

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

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

        if (x == x1 && y == y1) {
            cout << dist << '\n';
            return 0;
        }

        for (int dir = 0; dir < 8; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            pair<int, int> np = {nx, ny};
            auto it = allowed.find(np);
            if (it != allowed.end()) {
                allowed.erase(it);
                q.push({np, dist + 1});
            }
        }
    }

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

7. Код на Python 3

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    x0 = next(it)
    y0 = next(it)
    x1 = next(it)
    y1 = next(it)

    n = next(it)

    allowed = set()
    for _ in range(n):
        r = next(it)
        a = next(it)
        b = next(it)
        for c in range(a, b + 1):
            allowed.add((r, c))

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

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

    q = deque()
    q.append((x0, y0, 0))
    allowed.remove(start)

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

    while q:
        x, y, d = q.popleft()
        if (x, y) == target:
            print(d)
            return

        nd = d + 1
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            np = (nx, ny)
            if np in allowed:
                allowed.remove(np)
                q.append((nx, ny, nd))

    print(-1)

if __name__ == "__main__":
    main()