Algorytm znajdowania drogi z labiryntu.

Question

Witajcie! 
Mam pewien problem. Otóż muszę rozwiązać pewne zadanie na zaliczenie. Znajduje się ono na stronie themis.lo14.wroc.pl:

Dla danego opisu labiryntu odpowiedz, czy istnieje droga do wyjścia, gdzie 1 oznacza ścianę, zero oznacza korytarz (pole, przez które możemy przejść) a 2 oznacza wyjście. Startujemy zawsze, ale to zawsze w lewym górnym rogu.

Wejście

na samym początku dwie liczby n,k <=100 n oznacza liczbę wierszy (n jak wiersze) a k liczbę kolumn (k jak kolumny), w kolejnych n wierszach jest po k liczb pooddzielanych spacjami opisujących labirynt.

Wyjście

1 jeśli da się przejść przez labirynt, 0 w przeciwnym przypadku.

Przykład

Dla danych wejściowych

3 11
0 0 0 1 0 0 1 1 0 0 0 
0 0 0 1 0 0 0 0 0 1 0 
0 0 0 0 0 0 1 0 0 0 2 

poprawną odpowiedzią jest

1

 

Nie mam pojęcia jak się do tego zabrać. Mógłby ktoś mnie w jakiś sposób nakierować czego użyć, żeby poradzić sobie z tym zadaniem.

Answer 1

Algorytm dijkstry np http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

http://www.geeksforgeeks.org/shortest-path-in-a-binary-maze/  zarówno wyjscie z labiryntu jak i szukanie najkrótszej z dróg.

Algorytmy BFS,DFS także możesz przeglądnąć

Comments

Jeśli wszystkie odledłości/"trudność" w labiryncie są takie same (a tutaj tak jest), algorytm dijkstry degraduje się do BFSa - więc najlepiej zacząć od niego lub DFSa, bo są trochę prostsze.

(Potem jeszcze opcjonalnie A*.)

---

No właśnie A* też fajny, tylko - podejrzewam, że raczej tutaj chodziło o te prostsze algorytmy właśnie typu BFS

Answer 2

Kiedyś napisałem program Pathfinder, który za pomocą algorytmu przeszukiwania sąsiadujących pól znajduje ścieżkę najkrótszego przejścia. Program ładnie pokazuje jak ten algorytm działa i jest opisany i dostępny na mojej stronie obliczeniowo.com.pl/?id=PathFinder - znajdowanie najkrótszej ścieżki

Uproszczony algorytm znajdowania ścieżki zaimplementowałem w gierce napisanej w  JavaScipt-cie obliczeniowo.com.pl/?id=Gra Mordercze Działka napisana w JavaScript

Tutaj krótki filmik pokazujący działanie programu

https://www.youtube.com/watch?v=9fZhoPan4Rc

Comments

Ładne. Gdyby kod był na githubie to bym spojrzał :P

Podobna wizualizacja w przeglądarce:

https://qiao.github.io/PathFinding.js/visual/