Rezultati

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

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 10/10 14,008 MiB 0,010 s OK
#2 [več] 10/10 14,633 MiB 0,015 s OK
#3 [več] 10/10 20,016 MiB 0,050 s OK
#4 [več] 10/10 14,629 MiB 0,034 s OK
#5 [več] 10/10 14,008 MiB 0,039 s OK
#6 [več] 10/10 14,926 MiB 0,028 s OK
#7 [več] 10/10 14,074 MiB 0,022 s OK
#8 [več] 10/10 14,078 MiB 0,003 s OK
#9 [več] 10/10 14,094 MiB 0,022 s OK
#10 [več] 10/10 14,066 MiB 0,022 s OK

Ocenjevani program (Gozdovi.cpp):
#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<char>> field(250000);
vector<vector<int>> visited(250000);

void dfs(int x, int y, int h, int w)
{
    if(visited[x][y] == 1)
        return;
    
    visited[x][y] = 1;

    if(x + 1 < h && field[x + 1][y] == field[x][y])
        dfs(x + 1,y,h,w); 

    if(x - 1 >= 0 && field[x - 1][y] == field[x][y])    
        dfs(x - 1,y,h,w); 
    
    if(y + 1 < w && field[x][y + 1] == field[x][y])
        dfs(x,y + 1,h,w); 
    
    if(y - 1 >= 0 && field[x][y - 1] == field[x][y])
        dfs(x,y - 1,h,w);

    if(x + 1 < h && y + 1 < w && field[x + 1][y + 1] == field[x][y])
        dfs(x + 1,y + 1,h,w);

    if(x - 1 >= 0 && y + 1 < w && field[x - 1][y + 1] == field[x][y])
        dfs(x - 1,y + 1,h,w);
    
    if(x + 1 < h && y - 1 >= 0 && field[x + 1][y - 1] == field[x][y])
        dfs(x + 1,y - 1,h,w);

    if(x - 1 >= 0 && y - 1 >= 0 && field[x - 1][y - 1] == field[x][y])
        dfs(x - 1,y - 1,h,w);
}

int main()
{
    int h, w, r;
    char a;
    scanf("%d %d",&h,&w);
    a = getchar();

    while(h != 0 && w != 0)
    {
        r = 0;

        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                a = getchar();
                field[i].push_back(a);
                visited[i].push_back(0);
            }

            a = getchar();
        }

        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                if(visited[i][j] == 0)
                {
                    r++;
                    dfs(i,j,h,w);
                }
            }
        }

        for(int i = 0; i < h; i++)
        {
            field[i].clear();
            visited[i].clear();
        }

        printf("%d\n",r);
        scanf("%d %d",&h,&w);
        a = getchar();
    }
}