Розбір для Лабіринт
Памʼятайте, що цей розбір слід використовувати лише коли ви застрягли, і не копіювати код з нього. Будь ласка, поважайте автора задачі та автора розбору.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Надсилання офіційного розвʼязку до того, як ви самі розвʼяжете задачу, є порушенням, за яке можна отримати блокування.
Розбір розв'язку
Це класична задача пошуку найкоротшого шляху в незваженому графі (кожна клітинка — вершина, ребра — переходи між сусідніми вільними клітинками з однаковою "вагою" 1 крок). Найкоротший шлях у незваженому графі шукається алгоритмом обходу в ширину (BFS, breadth-first search).
Кроки розв'язку:
- Знайти клітинку
S— початкову вершину. - Запустити BFS від
S, зберігаючи для кожної клітинки відстань (кількість кроків) від старту; спочатку всі відстані невизначені (наприклад, ~-1~), відстань доSдорівнює ~0~. - Під час обходу переходити лише в межах сітки та лише у вільні клітинки (не стіни), яких ще не відвідано.
- Коли дійшли до
F(або одразу після завершення BFS), вивести знайдену відстань; якщо вона так і залишилась невизначеною — вивести ~-1~.
Складність — ~O(n \cdot m)~ за часом і пам'яттю, оскільки кожна клітинка обробляється не більше одного разу.
Типова помилка: використовувати DFS (обхід у глибину) замість BFS для пошуку найкоротшого шляху — DFS не гарантує мінімальну кількість кроків без додаткової модифікації (наприклад, ітеративного поглиблення), тому для цієї задачі саме BFS є природним і найпростішим рішенням.
Коментарі