Programozás‎ > ‎Feladatok‎ > ‎

Szökés

Egy börtönben bizonyos rabok össze vannak láncolva, hogyan nehezebb legyen megszökniük. Egy lázadó csoport mégis úgy döntött, hogy megkísérlik a szökést. A terv egyik fontos eleme, hogy valamikor meg kell nyomniuk (pontosan egy időben) két egymástól távol lévő gombot. A csoportnak el kell döntenie, hogy melyik két rab a leginkább alkalmas erre a feladatra.

A rabokat összekötő láncok hosszának ismeretében adjuk meg a maximális távolságot, amennyire (valamelyik) két rab el tud távolodni egymástól. Ha nem korlátos a távolság, akkor -1 írandó ki.  

Feladat

Írjunk programot, ami megadja a maximális elérhető távolságot, amit két megfelelően megválasztott rabbal elérhető.

Bemenet

A bemenet N darab karakterláncban kódolja a rabok közötti láncok hosszát. A j. sor i. karaktere az i. és j. rab közötti lánc hosszát adja meg:
  • '0'-'9': a számjegy értéke  a távolság, 0-tól 9-ig
  • 'a'-'z': 10-től 35-ig
  • 'A'-'Z': 36-tól 61-ig
  • ' ': a szóköz azt jelenti, hogy a két rab nincs összeláncolva

Korlátok

  • a rabok száma 2 <= N <= 50
  • minden bemeneti sor N karakterből áll 
  • a bemeneti mátrix szimmetrikus, a főátlóban 0-ák vannak 
  • a bemeneti karakterek a fenti listából valók

Kimenet

Egyetlen szám a maximális elérhető távolság. Ha nem korlátos a táv, akkor -1-et kell kiírni.

Példák

Bemenet  Kimenet
"0568"
"5094"
"6903"
"8430"		8
"0 "
" 0"		-1
"0AxHH190"
"A00f3AAA"
"x00     "
"Hf 0  x "
"H3  0   "
"1A   0  "
"9A x  0Z"
"0A    Z0"		43
"00"
"00"		0


Címkék

Algoritmusok: legrövidebb út az összes pontpárra, Folyd-Warshall

megoldás