[Zadanie] Szukanie najkrótszej drogi

[tutorial]

Dane wejściowe

Legenda

litery [A...Z] - miasta
liczby [0...9999] - bramy

Zadanie

Napisz algorytm, który znajdzie najkrótszą drogę z dowolnie wybranej bramy do dowolnie wybranego miasta.

Zadady poruszania się między miastami

1) Twoją pozycję startową określa numer bramy;
2) Można być w kilku miastach jednocześnie (czyli jesteś w miastach o podanej bramie);
3) Przez bramy można przechodzić - koszt przejścia z miasta do miasta daną bramą wynosi 0;
4) Zmienić bramę w której się jest można tylko i wyłącznie z lewej do prawej czyli np. z bramy nr 1 można dojść do bramy tylko nr 2 w jednym kroku (koszt = 1).
5) Jeżeli nie da się przejść z bramy do miasta koszt = -1

Przykładowe dane wejściowe

Dane wyjściowe dla przykładu

Wyjaśnienie

1) Z bramy 1 idziemy do bramy 2 - koszt 1
2) Z gramy 2 idziemy do bramy 3 - koszt 1
3) Przechodzimy do miasta B - koszt 0
4) Wynik = 1+1+0 = 2
[/tutorial]

4) Zmienić bramę w której się jest można tylko i wyłącznie z lewej do prawej czyli np. z bramy nr 1 można dojść do bramy tylko nr 2 w jednym kroku (koszt = 1).

Co to znaczy z lewej do prawej? Bo można wziąć pod uwagę, że z lewej do prawej to kolejne liczby naturalne, albo kolejne liczby z podanego ciągu, np. dla bramy A:

1 2 3 4 5 2 3 2

Kolejne bramy z podanych ciągów.