![]() 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:
FeladatAdott 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 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.
BemenetA 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.
KimenetMinden 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éretekT ≤ 100;
Kis bemenetek
Nagy bemenetek
Példa
Tesztadatok
CímkékA feladat forrása: Google Code Jam, Qualification Round 2009
Algoritmusok: mélységi bejárás
megoldás |
Programozás > Feladatok >