Programozás‎ > ‎Feladatok‎ > ‎

Kevin Bacon játék

Barabási-Albert László, Mindentudás Egyeteme: "Craig Fass, Brian Turtle és Mike Ginelly, a pennsylvaniai Albright College diákjai 1994-ben kitaláltak egy látszólag egyszerű játékot, amely a mai napig lázban tartja az amerikai diákokat: arra jöttek rá, hogy Kevin Bacon, egy ismert hollywoodi színész, olyan sok filmben játszott, hogy mindegyik hollywoodi színész tipikusan két-három linken keresztül hozzá kapcsolható.

Például Tom Cruise csak egy lépésre van Bacontól, mert együtt játszottak az Egy becsületbeli ügy című filmben. Így Tom Cruise Bacon-száma 1. Mike Myersé kettő, mert össze van kapcsolva Robert Wagnerrel a Kicsikém című filmen keresztül. Wagner Bacon-száma 1, hála a Vad vágyaknak. De még olyan történelmi alakok is, mint Charlie Chaplin, összekapcsolhatóak Baconnel: Chaplin Barry Nortonnal játszott együtt a Monsieur Verdoux-ban, aki Robert Wagnerrel játszott a What Price Glory [A dicsőség ára] című filmben, aki, mint azt már tudjuk, egy linkre van Bacontől. Így Charlie Chaplinnek 3 a Bacon-száma. Glen Wasson és Brett Tjaden, két programozó egyetemi hallgató a University of Virginiáról azonnal felismerte, hogy a tetszőleges két színész közötti távolság meghatározása számítástudományi feladat. Wasson és Tjaden néhány heti programozással összerakta a The Oracle of Bacon weboldalt, amely a játék verhetetlen mestere lett. Ha tetszőleges két színész nevét begépeljük, akkor ezredmásodpercek alatt megadja a kettőjük közötti legrövidebb útvonalat, és kilistázza a színészek és filmek láncolatát, amelyeken keresztül kapcsolódnak. Rövid időn belül a weboldal napi húszezer látogatót számlált, és ezzel 1997-ben bekerült a Time által kiválasztott tíz legnépszerűbb oldal közé."

Feladat

Az IMDB (International Movie DataBase) adatai alapján határozzuk meg két színész távolságát! Adjunk is meg egy összekötő láncot, jelezve a közös filmeket is.

Példa

James Earl Jones -> Three Fugitives (1989) -> Jeff Perry (I) -> Wild Things (1998) -> Kevin Bacon (2)

Tesztadatok

Címkék

A feladat forrása: saját feladat
Algoritmusok: szélességi bejárás

megoldás