Programozás‎ > ‎Feladatok‎ > ‎

Vízgyűjtők


Geológusok fel szokták osztani a vizsgált területet különböző vízgyűjtő területekre.A felosztásban azok a pontok kerülnek azonos területhez, amelyekről az esővíz ugyanoda folyik.

Picit pontosabban a wikipedia alapján:

"A vízgyűjtő terület olyan terület, ahol a csapadékból és hóolvadásból származó víz lefelé folyik a helyi erózióbázis felé, leggyakrabban patakba, folyóba, tóba vagy tengerbe, de néha víznyelőbe. (Pl. Szlovéniában van sok ilyen búvópatak.) A vízgyűjtő területbe beletartoznak a területén átfolyó folyóvizek és a szárazföld, ahonnan a víz ezekbe folyik." 

Feladat

Adott egy táj "magasság-térképe", tehát egy olyan térkép, ami minden pontnak megadja a tengerszint feletti magasságát. Címkézzük fel a térképet úgy, hogy az azonos vízgyűjtő területhez tartozó pontok azonos betűjelet kapjanak!
  • Minden cellából a 4 élszomszéd egyikébe folyhat a víz, vagy maga a cella lehet víznyelő.
  • Akkor víznyelő egy cella, ha nincs nála alacsonyabb élszomszédja.
  • Ha nem víznyelő a cella, akkor legalacsonyabb szomszédja felé folyik a víz.
  • Ha több szomszéd azonos magasságú, akkor a következő sorrend szerinti első szomszéd felé folyik a víz: észak - nyugat - kelet - dél.
Minden cella egyértelműen hozzárendelhető egyetlen víznyelőhöz. A közös víznyelőhöz tartozó cellák alkotnak egy vízgyűjtő területet, ezeket kell azonos betűvel felcímkézni. Az északnyugati (bal felső) sarok mindig az 'a' címkét kapja, ezután sorfolytonosan haladva mindig az angol ábécé következő betűjét kell kiosztani, amikor új területet találunk.

Bemenet

A bemenet első sora a térképek számát adja meg:T. T térkép jön ezután, mindegyik két egésszel kezdődik - H és W - a magasság és a szélesség. A következő H sor a térkép sorait adja meg, minden sor W egész számot tartalmaz, a cellák magasságát nyugatról kelet felé haladva.

Kimenet

Minden tesztadathoz 1+H sor. Az első formája: "Case #X:" ahol X a teszteset sorszáma, 1-tól kezdve. A következő H sor a felcímkézett térkép, a bemenetnek megfelelő sorrendben.

Méretek

T ≤ 100;

Kis bemenetek

  • 1 <= H, W <= 10;
  • 0 <= magasságok < 10.
  • Legfeljebb két vízgyűjtő.

Nagy bemenetek

  • 1 <= H, W <= 100;
  • 0 <= magasságok < 10000.
  • Legfeljebb 26 vízgyűjtő.

Példa

Bemenet  Kimenet
5
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9
2 13
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
 Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a
Case #5:
a b c d e f g h i j k l m
n o p q r s t u v w x y z

Tesztadatok

Címkék

A feladat forrása: Google Code Jam, Qualification Round 2009
Algoritmusok: mélységi bejárás

megoldás