Лабиринт

Наявна матриця розміру M*N, що являє собою деякий лабіринт. Одна клітинка лабіринту є входом а інша виходом. Знайти найкоротший шлях від входу до виходу, якщо він існує.

Вхідні данні : файл Labirint.dat, де першим рядком йде два числа N та M (0<N,M<100), а далі M рядків по N чисел відокремлених пробілами. Всі числа Amn можуть приймати значення 1,2,3,4. 1 - ділянка, що можна пройти. 2 - стіна. 3 - вхід. 4 - вихід.

Вихідні данні: число T>0, яке дорівнює довженні найкоротшого шляху, або -1, якщо такого шляху не існує.

Аналіз задачі.

По-перше треба відмітити, що максимальний розмір лабіринту, не перевищує 10⁴ елементів, тобто весь набір даних можна розмістити в статичній пам'яті.

Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:

1. кожної клітинок i приписується число T - тимчасова мітка.
2. заводяться два списки "фронту хвилі" NF і OF, а також перемінна T (поточний час);
3. OF:={u1}; NF:={}; T:=1;
4. для кожної з вершин i, що входять у OF, проглядаються сусідні вершини j, і якщо T[j] = -2, то T[j]=T, NF=NF + {j}.
5. якщо NF = {}, то шлях не існує, перехід до кроку 8.
6. якщо одна з вершин збігається з u2, то знайдений найкоротший шлях довжини T, перехід до кроку 8;
7. OF:=NF; NF:={}; T:=T+1; повернення до кроку 4.
8. Відновлюємо шлях проходячи масив P, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.

Але цей алгоритм можна удосконалити якщо використовувати замість списків OF і NF одну чергу. Єдиним зміна стосовно попереднього алгоритму є те, що номер ітерації хвилі повинний містяться в кожнім елементі черги.

[ Назад | До змісту ]