Witam
Jak rozwiązalibyście poniższy problem?
Na planszy 2D znajduje się punkt A. Mogą na niej (planszy) być pola blokujące i nieblokujące. Myślę nad algorytmem, który znalazłby wszystkie pola, których najkrótsza odległość do punktu A to x.
Pierwsza myśl, która przychodzi to dla każdego pola znaleźć najkrótszą drogę algorytmem A*. Jednak wiadomo, że za optymalne by to nie było.
Pozdrawiam,
Z góry dziękuje za pomoc
Jeżeli chodzi ci o odnalezienie drogi w labiryncie (tablocy[y][x]) to:
Załóżmy, że punkt A to punkt startu, a punkt B to meta. Pole 0 to miejsce, po którym można się poruszać, a 1 to przeszkoda.
Zrób sobie strukturę:
struct punkt
{
bool aktywny; //sprawdzenie, czy struktura zostala zapelniona
int x; // x punktu
int y; // y punktu
int poprzedni_punkt; //id struktury punktu, od którego powstał nowy punkt
int dlugosc; //po każdym wykonaniu pętli dodaj 1
};
struct punkt p[ilosc_zer]; //zrób tyle struktur, ile jest zer w twojej tablicy
Następnie określ w punktach sx i sy współrzędne startu.
Gdy to zrobisz ustaw strukturę p[0] na aktywną, współrzędne p[0].x na sx, p[0].y na sy.
Kolejnym krokiem będzie pętla for(n = 0; n < ilosc_zer; n ++), wewnątrz której sprawdzać będziesz punkty sąsiadujące ze współrzędnymi w każdej strukturze. Jeżeli pole sąsiadujące =='0', to wyszukujesz wolnej (niezapisanej struktury) i przekazujesz jej x,y oraz ustawiasz poprzedni_punkt = n.
Każdą pozycję punktu na mapie oznaczaj jakimś unikalnym znakiem, który wykluczy "cofanie się".
Z pętli for wyjdź dopiero wtedy, gdy nowo powstały punkt ma identyczne współrzędne jak współrzędne mety. ID struktury zapisz do jakiejś zmiennej.
Aby teraz odczytać najkrótszą drogę musisz wczytywać od mety (czyt. ostatniego punktu, ID tego punktu masz zapisane w zmiennej). Zamień komórkę na jakiś znak i teraz swoją zmienną na "zmienna = p[zmienna].poprzedni_punkt;". Ponownie wczytaj punkt z nowej struktury i zmień zmienną na tej samej zasadzie jak poprzednio. Rób tak aż ID struktury będzie równe 0 (co oznacza, że doszedłeś do startu).
Znaki, które tworzyłeś od Mety do Startu wskażą Ci najkrótsza drogę. Jutro wkleję tu kod źródłowy tego programu, ponieważ teraz jestem w szkole a w domku neta niet.
Etit:
Przepraszam, nie doczytałem tematu. Rób tak samo, tylko wyłączaj punkty z uzytku po uzyskaniu odpowiedniej dlugosci.
A z pętli wyjdź wtedy, gdy wszystkie struktury będą dezaktywowane.
Zastosuj algorytm BFS, który idealnie nadaje się do twojego problemu.
Taki właśnie sposób wykonania opisałem powyżej