Сакурако та її подорож#407

Сакурако та її подорож (Розбір)

Автор:

Богдан Фейса

Підготовка завдання:

Богдан Фейса

Розбір:

Богдан Фейса

Блок : n,m\le 100:

Для першого блоку нашого завдання ми будемо перебирати кожну можливу відповідь (1\le k\le n), створювати матрицю n\times n і перевіряти, чи існує шлях від до , який не містить жодної клітини, що знаходиться ближче ніж на до будь-яких туристичних пасток. Це призводить до часової складності O(n\cdot(n^2+m)).

Блок : n,m\le 10^3:

Для другого блоку цього завдання ми збережемо техніку побудови матриці, але замість перебору кожної можливої відповіді ми будемо використовувати бінарний пошук, щоб знайти найбільше можливе , таке що існує шлях від до , який не містить жодної клітини, що знаходиться ближче ніж на до будь-яких туристичних пасток. Це призводить до часової складності O(\log{n} \cdot(n^2+m)).

Блок : n\le 10^3:

Цей блок має таке ж рішення, але тут нам потрібно використовувати bfs від усіх туристичних пасток, щоб позначити всі клітини, які знаходяться ближче ніж на до будь-якої туристичної пастки. Це призводить до часової складності O(\log{n} \cdot(n^2)).

Блок : або x_1=x_2=\dots=x_m або y_1=y_2=\dots=y_m:

Це блок, в якому ми могли б використовувати формулу, щоб спробувати пройти від до між кожною парою найближчих туристичних пасток. Часова складність або O(m\log{m}+m\log{n}), або O(m\log{m}+m).

Блок : повне рішення:

Ми створимо граф з m+4 вершин. Кожна з перших вершин позначає туристичну пастку. Інші вершини позначають межі матриці. (m+1 - верхня, m+2 - ліва, m+3 - нижня, m+4 - права)

Ми створимо ребро між парою перших вершин, якщо немає шляху від до , який проходить між цими двома туристичними пастками, не проходячи через жодну клітину, відстань до якої від туристичної пастки менша ніж . Також ми спробуємо з'єднати перші вершин з іншими : якщо ця туристична пастка ближча до межі ніж , то ми додаємо ребро. Тепер, якщо існує шлях від m+1 до m+2 або від m+1 до m+3 або від m+2 до m+4 або від m+3 до m+4, то немає можливості пройти від до з даним .

Загальна часова складність O(m^2\log{n}).