maybe you can read more on dynamic programming first, it is about how to
divide the problem into smaller piece of elements recursively.
simple example - write a factorial function N!
int factorial(int N)
{
//bounday or stopping condition
if (N<=1)
return 1;
//here, try to process 1 step explicitly, and leave the
//remaining jobs to the recursive function
return N * factorial(N-1);
}
as you can see, to formulate a recursive function or algorithm, you need to
know what can be done "repeatedly" or recursively.
In graph problem, sometimes the decision cannot determine on the cell
itself, it relies on neighbours.
But the decision of neighbours also relies on their neighbours.. there is a
repeat pattern, thus in general, you can write something like this:
//pseudo code
void DoSomething(graph g, position p)
{
//similarly, you have boundary or stopping condition
if (stopping condition satisfied)
return;
//try to process 1 step and leave the remaining jobs to
//the recursive function
for (n = neighbour of p in g)
{
//do something
.............
//pass on to recursive function to solve remaining
DoSomething(g, n);
}
}
So, you need to analyse the question and determine the part of recursion,
then implement the code. That is the very first step. After you know the
technique, then try to learn how to optimise the algorithm, since you can
solve the question using different ways of recursion, together with suitable
data structure and use of memory.
On Sat, Sep 5, 2009 at 2:59 PM, CodeJunky <[email protected]>wrote:
>
> thanks buddy!!!!!!
> im actually new in coding arena ..........well i understood the
> problem and sawmany implementations
> the thing is i have read quite a few graph algorithms but im unable to
> implement them in any problem
> since i donot have any other mentor or tutor ..........forums are the
> only source of learning
> I went through the top coder tutuorial of graph but i could not
> understand the problems discussed
> can anyone give me links to some straightforward problems so that
> gradually i reach a level where
> i can comprehend and code any graph problem
>
> thanks and regards!!!
>
> On Sep 5, 10:24 am, Hawston LLH <[email protected]> wrote:
> > 1. start from top to bottom, left to right, check each cell one by one.
> If
> > current location is already labelled, then label the locations stored
> > previously in the path with that label. Then clear the path vector and
> > continue step 1.
> > 2. otherwise, check north, west, east, south neighbour and get the
> minimum
> > location (x_min, y_min)
> > 3a. if min location is different from current location, then push/store
> > current location into the path vector and proceed to step 1 with the min
> > location.
> > 3b. otherwise, meaning current location is a sink, label it with next
> > char C' and also label all locations stored previously in the path vector
> > with C'.
> >
> > On Fri, Sep 4, 2009 at 7:37 PM, CodeJunky <[email protected]
> >wrote:
> >
> >
> >
> > > Can anyone please explain me the water shed problem and the graph
> > > approach
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
