--> Archiwum Forum
tomazzi [ Episode: 3 ]
Potrzebna pomoc. C
Mam do napisania program:
Labirynt. Dana jest macierz nxm zawierająca opis labiryntu. Opis składa się z trzech symboli o,x,*. "o" oznacza drogę, którą można przejść, "x" ścianę (blokadę), a "*" - kwiatek leżący na drodze (można przechodzić przez kwiatek). Znaleźć drogę (jeśli istnieje) z jednego końca labiryntu na drugi zawierającą najwięcej kwiatków (jeżeli istnieje kilka dróg wybrać tę najbardziej ukwieconą).
Może ktoś coś podobnego pisał w C. Chętnie przyjmę wszelkie porady a jak ktoś ma dostępny to także kod.
Planuje zrobić to tak że sprawdzanie będzie sie zaczynać z punkty 0,0 i kończyć na punkcie n,m. Sprawdzanie rekurencyjne, sprawdza każdy punkt wokół danego.
Jeszcze nie zacząłem pisać więc może ktoś podzieli sie swoimi spostrzeżeniami.
Toolism [ GameDev ]
Nie pisz tego brute forcem:) Proponuję zainteresować się algorytmem A*, sluzy do wyszukiwania scieżek w grafie. Możesz zakombinować z kosztami i np priorytyzować te komórki które mają kwiatek i są przejezdne.
Pozdrawiam:)
tomazzi [ Episode: 3 ]
UPne w imię miłości
tomazzi [ Episode: 3 ]
Świąteczny UP
tomazzi [ Episode: 3 ]
Jak tak czytam to zadanie to dochodzę do wniosku że ono nie ma sensu. Bo jeżeli mam znaleźć najbardziej ukwieconą drogę to mogę przejść cały labirynt i wszystkie kwiatki odszukać.
Regis -> w 1 poście jest cała treść
Regis [ ]
A nie ma tam czasem warunku, ktory zabrania cofania sie, czy cos takiego?
Bo bez tego to faktycznie nie ma sensu :P
tomazzi [ Episode: 3 ]
Zaczynam pisać :P jak ktoś jeszcze ma jakieś pomysły to niech śmiało pisze ;)
Scatterhead [ łapaj dzień ]
najprościej i najniewydajniej jest to zrobić algorytmem z nawrotami.
Tworzysz funkcje rekurencyjna, która operuje na globalnej tablicy, a pamięta ostatni ruch oraz ścieżkę, na której się znajduje.
1. Funkcja oblicza wszystkie dozwolone ruch
2. Jeżeli tego ruchu nie ma, wychodzimy z funkcji. Jeżeli dotarliśmy do końca zapisujemy naszą sciężkę do wyniku.
3. Jeżeli takie ruchy są - dla każdego ruchu: robimy ten krok i wywołujemy rekurencyjnie naszą funkcje. następnie, cofamy ten krok.
mniej więcej jakoś tak :)
tomazzi [ Episode: 3 ]
A sobie UPne jeszcze raz. Drogi z początku do mety jakoś znajdę ale mam problem z ich zapamiętywaniem. Bo jak znajdę wszystkie to sobie wybiorę tą najbardziej ukwieconą i gotowe. Tylko nie wiem w co wrzucać te wszystkie drogi. Macie pomysł?
tomazzi [ Episode: 3 ]
Właśnie dowiedziałem sie że możliwe jest cofanie:) Macie jakieś pomysły w związku z tym?