Friday, December 31, 2010

UVA - 572 - Oil Deposits

problem statement

graph algorithms, finding number of components using DFS or BFS


If you read the problem statement carefully you can see that you have to find the number of components of a graph, I use DFS to do that.

in body of main :
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if( grid[i][j] == '@' && mark[i][j] == false )
                    dfs( i, j ), comp ++;

void dfs( int r, int c )
{
    mark[r][c] = true;
    for(int i = r-1; i <= r+1; i ++)
        for(int j = c-1; j <= c+1; j ++)
            if( inRange( i, j ) && grid[i][j] == '@' && mark[i][j] == false )
                dfs( i, j );
}

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...