optymalizacje, o ktorych mowisz przyspiesza bruta tak na oko dwukrotnie ;).
zadanie wyglada tak: na polu sa rozmieszczone odstraszacze żab, żaba przechodzi przez nie jak najdalej od odstraszaczy. wypisz kwadrat (tw. pitagorasa) odleglosci od najblizszego odstraszacza, obok ktorego prszeszla zaba. W szczegolnosci zero.
Blad (tak mysle) polegal na obliczaniu mapy odleglosci - nie sprawdzilem jakiegos warunku i nie liczyl jej dokladnie - pola odstraszania to okregi, ja pierwotnie robilem romby, potem jeszcze jakos to ulepszylem, ale jak widac niedostatecznie. Tak czy inaczej generowanie mapy w tym przykladzie trzeba inaczej zrobic
precyzujac moje rozwiazanie (rzeczywiscie to co podalem wymaga jeszcze zastanowienia jak mape przygotowac) - algorytm "mądrze" zachłanny:
1 generujemy mape
2 zerujemy tablice odwiedzono (bool)
3 dodajemy punkt startowy do kolejki priorytetowej i oznaczamy jako odwiedzoony, zapisujemy jako wartosci po prostu wartosc z mapy
4 1 petla (dopoki jest cos w kolejce)
4 2 bierzemy punkt z kolejki o najnizszej wartosci
4 3 petla (wszyscy nieodwiedzeni sasiedzi)
4 4 1 oznaczamy jako odwiedzony
4 4 2 do wartosci na mapie dodajemy wartosc zdjeta z kolejki priorytetowej w 4.2
4 4 3 dodajemy punkt do kolejki z wartoscia jako wlasnie wyliczona wartoscia z mapy
4 4 4 jezeli punkt jest punktem konca to przerwij petle i podaj wynik
5 jezeli petla sie zakonczyla bez podania wyniku, to droga nie istnieje
złożoność pesymistyczna (pomimo dwoch pętli) - O(n), gdzie n to ilosc pol. Poniewaz kazde pole jest wrzucane do kolejki najwyzej raz. Do optymalizacji można pominąć zapis wartości na mapę, ale wydrukowanie mapy pozwala na łatwiejsze debugowanie - punkty 4.4.2 i 4.4.3 skladaja sie w jeden
uzasadnienie czesci algorytmu mozna by bylo zerznac bezposrednio od dijkstry :)