Сжатие координат

Question

Проблема: у вас есть сетка N x N (1 < = N < = 10^9). Каждый квадрат может быть пройден или заблокирован. Есть M (1 < = M < = 100) препятствия в сетке, каждая из которых имеет форму 1xK или Kx1 полосы квадратов сетки. Каждое препятствие задается двумя конечными точками (A_i, B_i) и (C_i, D_i), где A_i = C_i или B_i = D_i. Вам также присваивается начальный квадрат (X, Y). Вопрос в том, сколько квадратов доступно от стартовой площади, если вы можете идти влево, вправо, вверх и вниз, и вы не можете преодолевать препятствия?

Я попытался решить эту проблему с помощью BFS, но для очень больших размеров сетки это слишком медленно. Затем я услышал о сжатии координат. Может кто-нибудь объяснить, что такое сжатие координат, как оно реализовано, где я могу узнать больше об этом?

Answer 1

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

Идея состоит в том, чтобы уменьшить количество квадратов на графике, создав прямоугольные блоки из квадратов. Чтобы проиллюстрировать это, вы хотите, чтобы преобразовать ваш график, как это:

Это уменьшает количество вершин сильно. Например, 5 квадратов в верхнем левом углу теперь представлены одним блоком. Новый график имеет только 7 × 7 блоков.

Должно быть легко достичь такого представления: найти координаты горизонтального и вертикального блоков. Сортируйте их. Используйте бинарный поиск, чтобы найти блок-координаты препятствий и отправную точку. Затем используйте свой оригинальный алгоритм на сжатой сетке.