Tűzoltók

A Belvárosi Tűzoltóság együttműködési szerződést kötött egy szállítási vállalattal, amely a város utcáinak aktuális állapotáról készített térképekkel látja el őket. A városban több utca is le van zárva átalakítások és építkezések miatt. A tűzoltóknak ki kell választaniuk azokat az útvonalakat, amelyek a tűzoltó állomásoktól a tűz helyéig vezetnek, és elkerülik a lezárt utcákat. A város körzetekre van osztva, és minden körzet tartalmaz egy tűzoltó állomást. Tűz esetén a diszpécser riadóztatja a megfelelő körzeti állomást, és megadja a lehetséges útvonalakat az állomástól a tűzig. Írjunk programot, amely meghatározza ezeket a lehetséges útvonalakat!

Bemenet:

A város minden körzetéhez tartozik egy térkép. A körzeten belül az útkereszteződések egy-egy pozitív egész számmal vannak azonosítva; ezek egyike sem nagyobb húsznál. A körzeti tűzoltóállomás azonosítója minden esetben 1. Az INPUT.TXT állomány különböző tesztadatokat tartalmaz az egyes körzetekről. Minden adatsor első sora tűzhöz legközelebbi útkereszteződés azonosítóját tartalmazza. Az ezt követő sorok mindegyike két pozitív egészet tartalmaz; a nem lezárt utcák által összekötött útkereszteződések azonosítóit. Ha például a 4 7 pár szerepel e sorok között, akkor a 4 és 7 jelzető kereszteződések közti utca nincs lezárva. Az utcán más kereszteződés nincs. Az egyes tesztadatokat két darab 0 zárja le.

Kimenet:

Az egyes körzetekhez tartozó eredményeket sorszámozva (Teszt #1, Teszt#2, stb) írjuk az OUTPUT.TXT állományba! Listázzuk ki az összes lehetséges útvonalat a tűzoltóállomástól a tűzig. Természetesen csak a körmentes utakat kell kilistázni, azaz azokat, amelyek egyetlen útkereszteződést sem érintenek egynél többször. Végül írjuk ki a tűzoltóállomástól a tűzig vezető lehetséges utak számát is!

Példa:

INPUT.TXT

OUTPUT.TXT

6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0

Teszt #1
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
Utak száma a 6 csúcsig: 7
Teszt #2
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
Utak száma a 4 csúcsig: 8

 

 

 

 

 

 

 

(ACM döntő 1991)