Rezultati

Up. imeNalogaJezikRezultatČas oddaje
cimpricevi-angelcki-2019 Gozdovi C++ 100/100OK 24. apr '19 @ 19:24

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 2,996 MiB 0,004 s OK
#2 [več] 10/10 3,531 MiB 0,034 s OK
#3 [več] 10/10 3,527 MiB 0,027 s OK
#4 [več] 10/10 3,527 MiB 0,034 s OK
#5 [več] 10/10 2,996 MiB 0,000 s OK
#6 [več] 10/10 3,484 MiB 0,046 s OK
#7 [več] 10/10 3,016 MiB 0,008 s OK
#8 [več] 10/10 3,172 MiB 0,039 s OK
#9 [več] 10/10 3,047 MiB 0,034 s OK
#10 [več] 10/10 3,031 MiB 0,038 s OK

Ocenjevani program (gozdovi.cpp):
/*

Dobili ste satelitske slike slovenskih gozdov. Slika je karirasta mreža, ki je sestavljena iz kvadratov velikosti 1 km×1 km. Za vsak kvadrat (s površino 1 km2) je označeno, katere vrste dreves prevladujejo na njem. Za vsako satelitsko sliko morate povedati, koliko različnih gozdov se nahaja na njej. Gozd je definiran kot največje povezano območje iste prevladujoče vrste dreves. Dva kvadrata dreves sta sosedna, če si delita stranico ali oglišče.
Vhodni podatki

V prvi vrstici sta dani s presledkom ločeni nenegativni celi števili n1 in m1. Sledi slika velikosti n1×m1. Slika je sestavljena iz n1 vrstic; vsaka vrstica vsebuje m1 znakov, ki označujejo prevladujoči gozd na pripadajočem kvadratu. Nato sledita s presledkom ločeni nenegativni celi števili n2 in m2 ter nova slika velikosti n2×m2. Vhod se zaključi, ko velja ni=mi=0.
Omejitve vhodnih podatkov

    0≤nj,mj
    ∑jnjmj≤250000
    Prevladujoče vrste dreves so označene z velikimi črkami angleške abecede.

Izhodni podatki

Za vsako sliko izpišite po eno vrstico, ki naj vsebuje število gozdov na njej.
Primer
Vhod

4 5
BHHHK
HBHKK
LLLLL
GGLGG
1 3
JJJ
0 0

	
Izhod

6
1

Komentar

Na prvi sliki proti severozahodu vidimo brezov gozd, ki se prepleta s hrastovim, toda na vzhodu se ta začne prelivati v kostanjev gozd. Južno od tega je pas, primeren za rast lipe, ki se dovolj zajeda v obronke gabra na jugu, da ga je razdelila v dva ločena gozdova. Na sliki tako vidimo 6 gozdov: bukovega, hrastovega, kostanjevega, lipovega in dva gabrova. Na drugi sliki imamo samo jesenov gozd.

*/


#include <iostream>


int V[250003];


int DX[8] = { 1, 1,  1, 0,  0, -1, -1, -1 };
int DY[8] = { 0, 1, -1, 1, -1, -1,  0,  1 };

int n, m;

int floodfill(int row, int col, int znak)
{
    if (row < 0 || col < 0 || row >= n || col >= m) return 0;

    int idx = row * m + col;
    if (V[idx] != znak || V[idx] < 0) return 0;

    V[idx] = -znak;

    for (int i = 0; i < 8; ++i) {
        
        int c = col + DX[i];
        int r = row + DY[i];
        floodfill(r, c, znak);
    }

    return 1;
}


int main()
{
    std::cin >> n >> m;

    while (n != 0 && m != 0) {
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                int idx = row * m + col;
                char c;
                std::cin >> c;
                V[idx] = c;
            }
        }

        int vsota = 0;
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                int idx = row * m + col;
                vsota += floodfill(row, col, V[idx]);
            }
        }

        std::cout << vsota << '\n';

        std::cin >> n >> m;
    }

    return 0;
}