- tablicę \(\displaystyle{ n \cdot n}\) punktów
- listę obszarów zabronionych w kształcie prostokątów
- dwa punkty
Jedyny pomysł to sprawdzenie wszystkich możliwości postaci łamanych pomiędzy punktami i wierzchołkami obszarów zabronionych, sprawdzenie które są dopuszczalne, a które przez te obszary przechodzą i na koniec znalezienia miniumum.
Jednak nie uśmiecha mi się pisanie go(chyba, że nie będzie innego wyjścia :p ), więc mam takie pytanie czy ktoś już napisał kiedyś taką funkcję i jest ona w jakieś bibliotece C++/ albo jest jej pseudokod gdzieś w internecie? Prawdopodobnie będzie trzeba ułożyć graf z tych wierzchołków i znalezienie algorytmem Dijkstry najkrótszą ścieżkę.
Edit. Algorytm DiJkstry znajdę, bardziej mi chodzi o sprawdzanie czy ścieżka jest dopuszczalna, czy zabroniona.