Informatika gyűjtemény

Egy szinttel feljebb uj_vgy.cpp

2004050607080910

<<  18. óra  >>

<<  Vízgyűjtők  >>

NézetNyomtat

uj_vgy.cpp (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 3 KB
/*
    Informatika: algoritmus szakkor
    Feladat: Vizgyujtok
    Forras 1: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/18ora/vizgyujtok
    Forras 2: http://code.google.com/codejam/contest/dashboard?c=90101#s=p1
    Uray M. Janos, 2010. februar 26.
*/
#include <iostream>
#include <fstream>
using namespace std;

#define MaxMap      100
#define MaxW        100
#define MaxH        100
#define MaxAlt      9999
#define MaxLabel    26

// Egy terkep
struct sMap {
    // Szelesseg, magassag
    int H, W;
    // Mezok
    struct sField {
        // Mezo magassaga
        short Alt;
        // Az a mezo, ahova innen a viz tud folyni (ha tud)
        char ToX, ToY;
        // Mezo cimkeje
        char Label;
    } Field[MaxH][MaxW];
};

bool Read (const char *, int &, sMap *);
bool Write (const char *, int, const sMap *);

bool FindLowestNeighbour (sMap &, int, int, int &, int &);
void Solve (sMap &);
void SortLabels (sMap &);

int main (int nArgs, char * Arg []) {
    sMap Map;
    int Num, I, J, K;
    // Argumentumok ellenorzese, allomanyok megnyitasa
    if (nArgs < 3)
        return 1;
    fstream Fin(Arg[1], fstream::in), Fout(Arg[2], fstream::out);
    if (Fin.fail() || Fout.fail()) {
        Fin.close();
        Fout.close();
        return 1;
    }
    Fin >> Num;
    for (I = 0; I < Num; I++) {
        // Terkep beolvasasa
        Fin >> Map.H >> Map.W;
        for (J = 0; J < Map.H; J++)
            for (K = 0; K < Map.W; K++)
                Fin >> Map.Field[J][K].Alt;
        // Terkep jelolese
        Solve(Map);
        // Terkep jeloleseinek megfelelo rendbe tetele
        SortLabels(Map);
        // Terkep mentese
        Fout << "Case #" << I + 1 << endl;
        for (J = 0; J < Map.H; J++) {
            for (K = 0; K < Map.W; K++)
                Fout << Map.Field[J][K].Label << " ";
            Fout << endl;
        }
    }
    
    // Allomanyok bezarasa
    Fin.close();
    Fout.close();
    
    return 0;
}

// Egy adott terkep adott pontjara (X0; Y0) kitolti, hogy hova folyik onnan a viz (ToX; ToY).
bool FindLowestNeighbour (sMap & Map, short X, short Y) {
    short Min = Map.Field[Y][X].Alt;
    // Eszak
    if (Y > 0 && Map.Field[Y - 1][X].Alt < Min) {
        Min = Map.Field[Y - 1][X].Alt;
        Map.Field[Y][X].ToX = X;
        Map.Field[Y][X].ToY = Y - 1;
    }
    // Nyugat
    if (X > 0 && Map.Field[Y][X - 1].Alt < Min) {
        Min = Map.Field[Y][X - 1].Alt;
        Map.Field[Y][X].ToX = X - 1;
        Map.Field[Y][X].ToY = Y;
    }
    // Kelet
    if (X + 1 < Map.W && Map.Field[Y][X + 1].Alt < Min) {
        Min = Map.Field[Y][X + 1].Alt;
        Map.Field[Y][X].ToX = X + 1;
        Map.Field[Y][X].ToY = Y;
    }
    // Del
    if (Y + 1 < Map.H && Map.Field[Y + 1][X].Alt < Min) {
        Min = Map.Field[Y + 1][X].Alt;
        Map.Field[Y][X].ToX = X;
        Map.Field[Y][X].ToY = Y + 1;
    }
    // Ha van olyan minimum, ahova tud folyni, akkor igazzal ter vissza
    return Min < Map.Field[Y][X].Alt;
}

// A pontok felcimkezese, nem feltetlenul a feladatban megadott sorrendben
// A sorrendet a kiiras (Write) fogja helyreallitani.
void Solve (sMap & Map) {
    int I, J;
    int Label = 0;
    int M;
    // Cimkek nullazasa ("minuszegyezese"), es viznyelok keresese es megjelolese
    // Viznyelok keresese es megjelolese
    for (I = 0; I < Map.H; I++)
        for (J = 0; J < Map.W; J++)
            if (FindLowestNeighbour(Map, J, I))
                Map.Field[I][J].Label = -1;
            else
                Map.Field[I][J].Label = Label++;
    // Minden lepesben megnezi minden mezore, hogy ahova folyik onnan a viz,
    // az meg van-e mar jelolve. Ha igen, akkor az elobbinek is ez lesz a jele.
    // A ciklus addig megy, amig volt uj cimkezes (M szamolja a cimkezeseket).
    do {
        M = 0;
        for (I = 0; I < Map.H; I++)
            for (J = 0; J < Map.W; J++) {
                Label = Map.Field[Map.Field[I][J].ToY][Map.Field[I][J].ToX].Label;
                if (Map.Field[I][J].Label == -1 && Label != -1) {
                    Map.Field[I][J].Label = Label;
                    M++;
                }
            }
    } while (M > 0);
}

// Cimkek helyretetele
void SortLabels (sMap & Map) {
    int I, J;
    char Lab[MaxLabel], Label = 'a';
    
    for (I = 0; I < MaxLabel; I++)
        Lab[I] = -1;
    
    for (I = 0; I < Map.H; I++)
        for (J = 0; J < Map.W; J++) {
            if (Lab[Map.Field[I][J].Label] == -1)
                Lab[Map.Field[I][J].Label] = Label++;
            Map.Field[I][J].Label = Lab[Map.Field[I][J].Label];
        }
}
(Vissza)