Zadanie do pogłówkowania

Home

Post ten stanowi pierwszy z serii, w której opisze podejście do rozwiązywania pewnej klasy problemów. W ostatnim czasie po raz kolejny zastosowałem to podejście do rozwiązania problemu, jaki napotkałem, i dlatego postanowiłem o tym napisać. Na początek proponuję zastanowić się nad takim zadaniem.

Treść zadania:

Załóżmy, że statek podróżuje pomiędzy pewną liczną N portów. Za każdym razem kiedy zawinie do portu jest to odnotowywane przez kapitanat w dzienniku. Kapitanat zapisuje również informacje o kolejnym docelowym porcie podróży.

Mając zbiór dzienników ze wszystkich portów, oraz port końcowy należy odtworzyć trasę podróży statku. Statek może wielokrotnie odwiedzać ten sam port. Statek może również wypłynąć z portu A i do niego wrócić.

Niestety dzienniki są prowadzone niechlujnie i nie możemy polegać na datach wpisów. Wpisy są natomiast ułożone chronologicznie w ramach dziennika, czyli jeśli wpis A jest wcześniej w danym dzienniku niż wpis B to znaczy, że statek najpierw odpłynął do A, wrócił po jakimś czasie i popłynął do B.

Przykład 1:

Rozważmy przypadek z 3 portami Szczecin, Gdańsk oraz Kołobrzeg. Portem końcowym jest Szczecin. Dzienniki dla pewnego statku wyglądają w następujący sposób:

Szczecin	Gdańsk	Kołobrzeg
Gdańsk	Kołobrzeg	Gdańsk
Kołobrzeg	Kołobrzeg	Szczecin
	Szczecin	Gdańsk

Z dziennika dla Szczecina możemy odczytać, że statek najpierw odpłynął do Gdańska potem wrócił i odpłynął do Kołobrzegu itd.

Rozwiązanie 1:

Rozwiązaniem jest następująca trasa:

Szczecin
Gdańsk
Kołobrzeg
Gdańsk
Kołobrzeg
Szczecin
Kołobrzeg
Gdańsk
Szczecin

Teraz w ramach ćwiczeń, zanim opiszę swoje podejście, proponuję rozwiązać problem dla poniższych danych. Port końcowy to Gdańsk.

Przykład 2:

Gdańsk	Szczecin	Kołobrzeg
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin