Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[Zadanie] Szukanie najkrótszej drogi

Ostatnio zmodyfikowano 2010-06-30 15:08
Autor Wiadomość
DejaVu
Temat założony przez niniejszego użytkownika
[Zadanie] Szukanie najkrótszej drogi
» 2010-06-30 02:49:50
[tutorial]

Dane wejściowe

brama_startowa miasto_docelowe
nazwa_miasta1 brama1 brama2 ... brama_n1
nazwa_miasta2 brama1 brama2 ... brama_n2
...
nazwa_miasta_x brama1 brama2 ... brama_nx

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

1 B
A 1 2 3 4 5 2 3 2
B 3 4 6 8 9
C 2 0 7 6 3
D 9 2 3 1

Dane wyjściowe dla przykładu

2

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]
P-18430
michalp
» 2010-06-30 10:23:17
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
P-18431
DejaVu
Temat założony przez niniejszego użytkownika
» 2010-06-30 15:08:08
Kolejne bramy z podanych ciągów.
P-18436
« 1 »
  Strona 1 z 1