Ja proponuję zrobić tak:
z tych stringów zrobić tablicę dwuwymiarową booleanów. jeśli jest ścieżka w punkcie [i,j] to wartość true, jeśli nie, to false.
dodatkowo zadeklarować sobie tablicę [1..64] rekordów [x,y] (rekord zawiera 2 integery które są współrzędnymi jakiegoś punktu)
37 00100101
136 10001000
196 -> 11000100
96 01100000
127 01111111 <- ten labirynt da się przejść.
37 00100101
42 00101010
42 00101010
np, dla tego labiryntu wartość [1,1] będzie false, [1,8] false, [3,1] true, itd (pierwsza współrzędna rośnie poziomo w prawo, druga pionowo w dół - 0,0 to górny lewy róg).
skonstruowanie takiej tablicy nie jest trudne - wystarczy utworzyć stringi z danych liczb w systemie (wystarczy włączyć bibliotekę STRUTILS, i można zamienić dowolną liczbę w sys. dziesiętnym na stringa zerojedynkowego, i nawet dodać ile się chce zer wiodących)
np.
Kopiuj
uses strutils;
var s: string; i: integer;
begin
read(i);
s:=binStr(i, 8);
end.
string 's' będzie zawierał zera i jedynki zapisane w 8 charach, z zerami wiodącymi.
potem wystarczy skanować ten string, i ustawiać w tablicy odpowiednie wartości - true/false.
i potem:
skanujesz sobie tę utworzoną tablicę. jeśli w jakimś miejscu [1, i] jest wartość true, to znaczy że można tutaj zacząć zwiedzanie labiryntu. zaczynasz więc zwiedzanie. jeśli z danego punktu prowadzi tylko jedna droga do innego punktu, to wymazujesz z tablicy aktualną pozycję (na aktualnej pozycji ustawiasz FALSE, zapewnia to potem stabilność programu i zapobiega zapętleniom przy powrotach do rozwidleń). sprawdzenie możliwych dróg można bardzo łatwo wykonać:
jeśli jesteś w punkcie [i,j] to wystarczy sprawdzić:
- [i-1,j]
- [i+1, j]
- [i, j-1]
- [i, j+1]
- jeśli w sumie na tych pozycjach jest więcej niż jedno true, to znaczy że z pozycji [i,j] prowadzi więcej niż jedna droga. analogicznie, jeśli nie ma żadnego true, znaczy że doszedłeś do ślepego zaułka. gdy dojdziesz do rozwidlenia, używasz tablicy rekordów o której wspominałem wcześniej. najlepiej trzymać zmienną dotyczącą tych rekordów, która będzie wskazywała na jakiej pozycji skończyłeś dopisywanie rekordów. np. jeśli dopisałeś 5 rekordów, to zmienna wskazująca na kolejne dopisanie=6. i po prostu gdy trzeba, odwoływać się do kolejnego rekordu (trzeba pamiętać o zwiększaniu 'wskazywacza' po każdym odwołaniu się do rekordu).
i teraz tak:
- jeśli jest jedna droga, to idziesz nią, i wymazujesz swój ślad.
- jeśli napotkasz się na rozwidlenie, dodajesz punkt w którym jest rozwidlenie, na pozycji w tablicy rekordów, którą wskazuje ci wskazywacz zapisywania. idziesz dowolnie wybraną drogą, i robisz analogicznie - gdy jest to jedna droga, wymazujesz, jeśli nie, zapisujesz współrzędne rozwidlenia. gdy dojdziesz do jakiegoś indeksu [8, i] to znaczy że wyszedłeś z labiryntu. jeśli dojdziesz do ślepego zaułka, to:
a) jeśli masz jakiś rekord wskazujący na rozwidlenie, sprawdzasz, w których kierunkach możesz z niego iść, i idziesz. jeśli nie ma żadnego kierunku w którym możesz iść, to wracasz do poprzedniego rozwidlenia, i tam sprawdzasz czy możesz iść, itd, aż nie będziesz miał żadnych rekordów wskazujących na rozwidlenia w tym korytarzu. w takim wypadku, skanujesz kolejne linie, aż natkniesz się na kolejne wejście do labiryntu które ma indeks [1, i], i tam wykonujesz to samo błądzenie.
b) jeśli nie ma już żadnych rekordów wskazujących na rozwidlenia, i żadnych innych wejść do labiryntu, odpowiedź brzmi nie.
c) jeśli doszedłeś do jakiegoś indeksu [8,i] (w sumie nawet nie trzeba do niego dochodzić - wystarczy, że dotrzemy do indeksu [7,i] i sprawdzimy czy w miejscu [8,i] jest TRUE - jeśli jest, to jest to wyjście z labiryntu) to odpowiedź brzmi TAK
jeśli masz jakieś pytania, to wal :P
przykładowy przebieg algorytmu dla tego labiryntu:
37 00100101
136 10001000
196 -> 11000100
96 01100000
127 01111111 <- ten labirynt da się przejść.
37 00100101
42 00101010
42 00101010
skanujesz tablicę. pierwszym wejściem jest [1,2] z którego prowadzi tylko jedna droga do [1,3]. w miejscu 1,2 ustawiasz FALSE aby nie próbować drugi raz wejść tym wejściem i się nie zapętlić. jesteś w 1,3, i robisz tak jak poprzednio. idziesz do 2,3 jedyną drogą, potem do 2,4 gdzie jest rozwidlenie (bo jest więcej niż jedna sąsiadująca komórka która ma TRUE). dodajesz współrzędne rozwidlenia do tablicy na pierwszej pozycji, jednocześnie w głównej tablicy ustawiając wartość FALSE w miejscu rozwidlenia. zwiększasz pozycję kolejnego zapisania na 2. idziesz dowolną drogą, przypuśćmy, że do 3,4. jedyna droga jest do 3,5, gdzie jest rozwidlenie. ustawiasz tam false, i dodajesz na pozycji drugiej współrzędne rozwidlenia. tym razem wybierasz drogę w dół, osiągasz punkt [3,8] który jest ślepym zaułkiem (po drodze trzeba pamiętać o wymazywaniu odwiedzonych ścieżek przez ustawianie FALSE). tak więc wracasz do ostatnio dodanego rekordu, którym jest nr 2. (aktualna pozycja zapisywania jest na 3, więc ostatnio dodany rekord jest na miejscu 3-1). tak więc wracasz do punktu 3,5 z którego prowadzi teraz dwie drogi - na prawo i na lewo. idziesz na lewo do 2,5. masz tylko jedną drogę do 2,4, gdzie jest ślepy zaułek (zauważ, że podczas wcześniejszego wykonywania algorytmu, wymazaliśmy ścieżki w miejscu 2,3 i 3,4, więc pozycję 2,4 program odczyta jako ślepy zaułek. wracasz w takim razie do 3,5. prowadzi z niego już tylko jedna droga, więc można wymazać ten rekord z tablicy, i ustawić pozycję zapisywania na 2 (na pozycji pierwszej mamy punkt 2,4 - gdybyśmy się do niej odwołali, to byłoby 0 możliwych ścieżek, i wymazalibyśmy go również - ale program tego nie wie, więc zostawia sobie ten rekord zapamiętany). idziemy więc z rozwidlenia 3,5 jedyną możliwą ścieżką, zamazując. dochodząc do 6,5 mamy rozwidlenie. zamazujemy go, dodajemy współrzędne tego rozwidlenia na poz. 2. idziemy w dół, gdzie jest ślepy zaułek. wracamy się więc do ostatnio dodanego rozwidlenia 6,5. i tym razem idziemy jedyną możliwą ścieżką. dochodzimy do 7,5. w tym miejscu, sprawdzając możliwe ścieżki, dowiadujemy się, że na pozycji [8,5] jest true, co jest równoznaczne z wyjściem z labiryntu. odpowiedź pozytywna.
