Cześć,
Czy ktoś mógłby mi wskazać jak rozwiązać problem przejścia labiryntu? Z tym że problem ten jest trochę utrudniony, ponieważ nie zawsze da się przejść od startu do celu bez konieczności wyburzania ścian. Algorytm ma wskazać nie tyle samą drogę co minimalną ilość ścian jakie należy wyburzyć. Na zajęciach nie mieliśmy jeszcze grafów tak więc tutaj nie musimy korzystać z rozwiązań tego typu. Raczej trzeba zastosować Backtracking/Bruteforce.
Wpadłem na dwa pomysły jednak żaden nie wydaje mi się optymalny:
- Usuwanie kolejno wszystkich kombinacji ścian i puszczanie za każdym razem algorytmu rozwiązującego klasyczny problem labiryntu. Czyli najpierw usuwam jakąś jedną ścianę, puszczam algorytm. Później poprzednią ścianę przywracam i usuwam następną. Jeśli znajdę rozwiązanie to zatrzymuje algorytm. Jeśli nie znajdę to usuwam ściany parami, jeśli to nie przyniesie efektu to po 3 ściany itd....
- Modyfikacja klasycznego algorytmu przechodzenia labiryntu, aby zamiast cofać się gdy napotka ścianę usuwał ją ale naliczał kosz takiej operacji. Natomiast zastanawiam się czy to w ogóle kiedykolwiek by się wykonało i nie zapętliło.
Szukam bardziej rozwiązania teoretycznego, z kodem sobie poradzę jeśli będę teoretycznie wiedzieć jak rozwiązać problem. Może mój problem ma dokładnie jakąś nazwę, o której nie wiem, też byłbym wdzięczny za jej wskazanie.