Rectangles are everywhere (Editorial)

Кроки мають довжину $0.5$, а прямокутники задані цілими координатами. Це зроблено навмисно: Андрійко може «протиснутися» між двома прямокутниками, якщо вони не стикаються, але не може пройти крізь місце, де вони торкаються один одного (навіть кутами).

Тому задача не про пошук шляху, а про пошук перешкоди. Шлях із кута $(0,0)$ у кут $(n,m)$ існує тоді й лише тоді, коли прямокутники не утворюють суцільної «стіни», що відділяє один кут від іншого.

Така стіна — це ланцюжок прямокутників, які попарно торкаються (або перетинаються) і сполучають дві протилежні щодо діагоналі частини межі кімнати: верхню разом із правою стороною — з нижньою разом із лівою.

Звідси алгоритм:

1. Побудуємо граф, вершинами якого є $k$ прямокутників. З'єднаємо два прямокутники ребром, якщо їхні межі мають спільну точку, тобто якщо їхні проєкції перетинаються по обох осях. Для прямокутників, заданих кутами, це перевіряється чотирма нерівностями.

2. Позначимо, які прямокутники торкаються верхньої або правої сторони кімнати, а які — нижньої або лівої.

3. Запустимо обхід (у глибину, у ширину або через систему неперетинних множин) від прямокутників першої групи. Якщо досягли якогось прямокутника другої групи — стіна існує, і Андрійко пройти не зможе.

Складність побудови графа «в лоб» — \mathcal{O}(k^2) пар, чого вистачає за помірних обмежень; сам обхід — лінійний від розміру графа.

Важлива деталь: прямокутники, що лише торкаються кутами, теж утворюють неперервну перешкоду, бо в цій точці немає навіть половини клітинки для проходу. Тому нерівності в перевірці мають бути нестрогими.