Witam,
czy jest ktoś w stanie wskazać mi algorytm dzięki któremu będę w stanie odnaleźć optymalną drogę w macierzy? Moje zadanie jest dosyć niestandardowe jeżeli chodzi o implementacje, dlatego, że muszę odnaleźć optymalną drogę w losowo wygenerowanej macierzy zero-jedynkowej (w okolicach 100x100), gdzie:
- "jednostka" poruszająca się przechodząc do kolejnego pola MUSI przejść do pola o wartości różniącej się (z 0 do 1 i odwrotnie). Inne przejście jest niemożliwe, jednostka nie może przejść z pola o wartości 1 do pola o wartości 1, z zerami podobnie.
- ustalenie startu drogi i jej końca nie ma większego znaczenia. Może być ustawione na "szytwno".
- w przypadku gdy jednostka jest otoczona polami o tej samej wartości - automatycznie nie może się poruszać i stoi w miejscu.
- gdy jednostka przechodząc, w pewnym momencie napotka te same wartości, ma się cofać tak długo, aż napotka pole o przeciwnej wartości na które może przejść.
Mam nadzieję że zrozumiecie mój być może nie jasny opis problemu ;). Można to jak najbardziej porównać do sposobu poruszania się dobrze znanego prymitywnego pantofelka, który może się poruszać tylko i wyłącznie z cząsteczki kwasowej do zasadowej i odwrotnie (z 0 do 1 oraz z 1 do 0).
Pozdrawiam