Vízgyűjtők
Forrás: Google Code Jam, Qualification Round 2009
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."
"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!
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 teszadathoz 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ő.
0 ≤ magasságok < 10.
Legfeljebb két vízgyűjtő.
Nagy bemenetek
1 ≤ H, W ≤ 100;
0 ≤ magasságok < 10,000.
Legfeljebb 26 vízgyűjtő.
0 ≤ magasságok < 10,000.
Legfeljebb 26 vízgyűjtő.
Példa
| ws.in | ws.out |
|
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 |