Mam zadanie mnie jwięcej tego typu
że jest pole prostokątne, na którym znajdują się inne prostokątne pola, nienakładające się, ani niestykające. Nalezy wyznaczyć najkrótszą ścieżkę z punktu A do punktu B, któe leżą na tym polu. I chodzi o to, że nie można chodzić po tych polach wewnętrznych (najwyżej po krawędziach), a żeby zastosować algorytm Dijkstry, trzeba wpierw stworzyć graf, z którego punktu (A, B, wierzchołki prostokątów) do którego, można się ruszyć.
Przychodzi mi do głowy tylko badanie położenia różnych punktów względem łączących inne punkty odcninków, ale implementacja i złożonośc mogą być nieco spore.
Any ideas?