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 );
}
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Friday, December 31, 2010
Subscribe to:
Post Comments (Atom)
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...
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
-
Prime Cryptarithm The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set ...
No comments:
Post a Comment