The End Dimension (Розбір)

Розв’язок

Спостереження:

• Клітини, з'єднані без проходження через перешкоди, утворюють компоненти зв’язності. Якщо початок і ціль у тій самій компоненті, телепортація не потрібна.

• Ніколи не вигідно використовувати більше ніж один телепорт.

Алгоритм:

1. Позначити всі компоненти зв’язності за допомогою DFS/BFS.

2. Запам’ятати, які компоненти містять телепорти.

3. Запустити BFS одночасно з усіх телепортів, щоб обчислити мінімальну відстань $d[i][j]$ до найближчого телепорта.

4. Для кожного запиту (x,y,b,c):

   • Якщо $(x,y)$ і $(b,c)$ у тій самій компоненті, відповідь $=0$.

   • Інакше, якщо обидві клітини належать компонентам із телепортом, відповідь $d[b][c]$.

   • Інакше, досягти неможливо, відповідь $=-1$.

Загальна складність: \mathcal{O}(n \cdot m + q).