Labirynt C

Prosze o pomoc w napisaniu programu w czystym C [???]

Program ma otrzymywać na wejściu dwie liczby (całkowite dodatnie) m i n oznaczające wymiary labiryntu, a następnie n linijek po m znaków ze zbioru {X,_,o}, przy czym znak 'o' ma występować dokładnie raz, gdzie X oznacza ścianę, _ oznacza korytarz, a o oznacza punkt początkowy. Można przyjąć, że 0<m,n<=100.
W labiryncie można poruszać się w czterech kierunkach: w górę, w dół, w prawo i w lewo - nie można poruszać się po skosie.
Wynikiem działania programu powinna być linijka zawierająca:

* liczbę będącą długością najkrótszej drogi, po której następuje spacja oraz ciąg znaków z alfabetu PLGD (Prawo, Lewo, Góra, Dół) wyznaczający taką drogę, o ile istnieje.
* łańcuch znaków: BRAK WYJŚCIA, gdy taka droga nie istnieje.

Użyty algorytm powinien działać w pesymistycznym czasie mn.

Na moje oko to musisz przerobić plansze na graf nieskierowany, nieważony i puścić w nim BFS'a i powinno zadziałać. Ale glowy nie daje, bo nie mam teraz czasu tego rysować i myślec nad tym ;)

Najpierw przypisujesz każdemu polu labiryntu pomocniczą zmienną(powiedzmy x) o wartości -1. Następnie odpalasz dla pola startowego rekurencyjną funkcję Odleglosc(start,0):

odleglosc(pole,x){
   pole->x = x;
   dla kazdego sasiedniego pola
    jesli sasiad->x > x+1 lub sasiad->x == -1
       odleglosc(sasiad,x+1)
}

Po zapuszczeniu tej funkcji, jeśli pole wyjściowe ma wciąż wartość x, ścieżka nie istnieje. W przeciwnym wypadku cofamy się z wyjścia do pola startowego (w każdym kolejnym kroku przechodzisz na pole o wartości mniejszej o 1 (jeśli są 2 takie pola, możesz wybrać dowolne, oznacza to istnienie dwóch ścieżek o równej długości). Kolejne kroki odkładasz na stos; na końcu ściągasz wszystkie ruchy ze stosu zamieniając je na przeciwne(prawo<->lewo, dół<->góra).

Podsumowując, zapuszczasz Dijkstrę dla grafu o wszystkich krawędziach z wagą równą 1.

Myślałem przez chwile czy Dijkstra tu nie pomoze, ale raz że chyba nie ma sensu używać go do grafu nieskierowanego i nieważonego. Dwa że jest też kwestia złożoności, a przecież Dijkstra ma większą (w przypadku pesymistycznym jak masz sporo relaksacji). A algorytm który podałeś bardziej wygląda właśnie na BFS niz na Dijkstre ;)