Help on recursive program!

[A.J]

Here's the code to one of my DFS functions.
I'm checking how many paths are there between 2 points on a grid of length 't'.
But, my ;count variable always returns 0, even though I'm increasing it when a solution is found (And there's a solution that is found, as you can see by my DEBUG Prints).
Here is the code :

C:

void DFS(int x, int y, int fx, int fy, int curp,int count,int t) {     if (curp<=t)     {         if (x==fx && y==fy)         { //            cout<<curp<<" "<<t<<endl;             if (curp==t)             {                 count+=1; //                cout<<count<<endl;             }         }             if (map[x][y]=='.')             {                 map[x][y]='*';                 DFS(x-1,y,fx,fy,curp+1,count,t);                 DFS(x+1,y,fx,fy,curp+1,count,t);                 DFS(x,y-1,fx,fy,curp+1,count,t);                 DFS(x,y+1,fx,fy,curp+1,count,t);                 map[x][y]='.';         }     } }

(P.S: Here is the code that calls the function:

C:

DFS(a1,b1,a2,b2,0,count,t);

where a1,b1 are the coords of the starting point and a2,b2 are the coords of the ending point)

[CodeMonkey2000]

Shouldn't you use pointers? In the function deceleration a copy of count is being created, even if count is global.

[A.J]

sooo....you're saying that I should.................(could you spell it out for me?)

[fishtastic]

A.J @ Tue Mar 25, 2008 8:12 pm wrote:

sooo....you're saying that I should.................(could you spell it out for me?)

his right, you passed in a copy of the variable, when you should have pass in the address of the variable as "&count"

[CodeMonkey2000]

There are two ways you can pass in variable into a function. The first is call by value. With call by value your original variable you passed in is safe from being manipulated by the function, since the variable in the function is independent from the variable you passed in to the function. The second way you pass in variable is called call by reference. This is when you pass in the address of a variable. With this method if you change the value of a variable you are actually changing what is stored in that memory location. So in a function if you pass in a memory location and manipulate it's information you are also manipulating the value of the variable you passed in. To call by reference in C++ we use pointers. Here is a simple swap function using call by reference:

code:

void swap(int * a, int *b) {        int tmp;        tmp=*a;        *a=*b;        *b=tmp; }

And here is how you would use it:

code:

int first;    int last;    cin>>first>>last;    swap(&first,&last);    cout<<first<<" "<<last;

Note: the ampersand(& sign) means the location of. The star( * sign) means that we are dealing with a pointer. And tmp=*a is one of the many things that doesn't make sense about C/C++ . *a is just how you manipulate values in C/C++ I guess.

[A.J]

here's my current code:

C:

void DFS(int x, int y, int fx, int fy, int curp,int *count,int t) {     if (curp<=t)     {         if (x==fx && y==fy)         { //            cout<<curp<<" "<<t<<endl;             if (curp==t)             {                 count+=1; //                cout<<count<<endl;             }         }             if (map[x][y]=='.')             {                 map[x][y]='*';                 DFS(x-1,y,fx,fy,curp+1,count,t);                 DFS(x+1,y,fx,fy,curp+1,count,t);                 DFS(x,y-1,fx,fy,curp+1,count,t);                 DFS(x,y+1,fx,fy,curp+1,count,t);                 map[x][y]='.';         }     } }

here is how i called it:

C:

DFS(a1,b1,a2,b2,0,&count,t);

it still ouputs the wrong answer (0).
(my algorithm seems wrong anyways)

[CodeMonkey2000]

Did you read my last comment? To manipulate values you need to do something like this:

code:

*count+=1;

It's one of those things that just doesn't make sense .

[md]

unless count is a measure of the depth of the recusion (I don't know, I'm not sure what teh algorithm is).

[zylum]

md @ Tue Mar 25, 2008 11:33 pm wrote:

unless count is a measure of the depth of the recusion (I don't know, I'm not sure what teh algorithm is).

A.J @ Tue Mar 25, 2008 9:27 pm wrote:

I'm checking how many paths are there between 2 points on a grid of length 't'.

Unless your map has a border of '*' characters, then you need to check whether your x and y variables fall within the bounds of the array. A more appropriate solution would look something like:

code:

dfs (int x, int y, int fx, int fy, int currentDepth, int targetDepth) : int     check if current position is in bounds of array and current pos is legal:         if current position corresponds with final position, return 1         else             set current position to visited             set returnVal to dfs(left of current pos, current depth + 1) + dfs(right, current depth + 1) + etc...             set current position to unvisited             return returnVal     return 0

[Saad]

CodeMonkey2000 @ Tue Mar 25, 2008 10:12 pm wrote:

There are two ways you can pass in variable into a function. The first is call by value. With call by value your original variable you passed in is safe from being manipulated by the function, since the variable in the function is independent from the variable you passed in to the function. The second way you pass in variable is called call by reference. This is when you pass in the address of a variable. With this method if you change the value of a variable you are actually changing what is stored in that memory location. So in a function if you pass in a memory location and manipulate it's information you are also manipulating the value of the variable you passed in. To call by reference in C++ we use pointers. Here is a simple swap function using call by reference:

code:

void swap(int * a, int *b) {        int tmp;        tmp=*a;        *a=*b;        *b=tmp; }

And here is how you would use it:

code:

int first;    int last;    cin>>first>>last;    swap(&first,&last);    cout<<first<<" "<<last;

Note: the ampersand(& sign) means the location of. The star( * sign) means that we are dealing with a pointer. And tmp=*a is one of the many things that doesn't make sense about C/C++ . *a is just how you manipulate values in C/C++ I guess.

That method is called passing by pointer. The following method is passing by reference in C++.

c++:

template <class Type> void Swap(Type &first, Type &second){     Type temp = second;     second = first;     first = temp; } int main(){     int a = 5;     int b = 10;     Swap(a,b);     std::cout << a << " " << b << std::endl; }

The & infront of the parameter means your passing it by reference and as a result you can modify the variable inside the function.
Although a decent C++ book should cover functions and you wouldn't need to ask this question.