You are using a version without Ads of this website. Please, consider donating:

Problem in Algorithm Recursive?

Hello friends, I have a problem to implement a recursive version of an algorithm that I made, I get different values, I hope you can help me, here are the code so Iterative (OK) and Recursive code form that is not OK.

The data sets do not give equal:

The algorithm is given two source and target positions on a board, find the number of paths between them...

Input Example: 5
2 3
4 4
Output Example:
 5

I hope its not help that I'm wrong!!!

Iterative Algorithm ( OK )
 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 #include #include #include #include #include #include #include using namespace std; int n , dp [1000][1000], x, y, xx, yy; bool mark [1000][1000]; struct Punto { int x; int y; }; Punto inicio, fin , aux; queue < Punto > lista; int direcciones[3][2] = { {0,1}, {1,0}, {1,1} }; void BFS() { lista.push(inicio); dp[ inicio.x ][ inicio.y ] = 1; while( !lista.empty() ) { aux = lista.front(); lista.pop(); x = aux.x; y = aux.y; for(int i=0 ; i<3 ; i++) { xx = direcciones[i][0]+x; yy = direcciones[i][1]+y; if( xx>0 && xx <= n && yy > 0 && yy <= n ) { dp[xx][yy] += dp[x][y]; if(!mark[xx][yy]) { mark[xx][yy] = true; aux.x = xx; aux.y = yy; lista.push( aux ); } } } } } int main() { cin>>n; cin>>x>>y; inicio.x = x; inicio.y = y; cin>>x>>y; fin.x = x; fin.y = y; BFS(); cout<< dp[fin.x][fin.y] <

Recursive Algorithm ( not OK )

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n , dp [1000][1000], x, y, xx, yy; bool mark [1000][1000]; struct Punto { int x; int y; }; Punto inicio, fin , aux; queue < Punto > lista; int direcciones[3][2] = { {0,1}, {1,0}, {1,1} }; void BFS(Punto aux){ x=aux.x; y=aux.y; for(int i=0;i<3;i++){ xx=direcciones[i][0]+x; yy=direcciones[i][1]+y; if( xx>0 && xx <= n && yy > 0 && yy <= n ) { dp[xx][yy] += dp[x][y]; if(!mark[xx][yy]) { mark[xx][yy] = true; aux.x = xx; aux.y = yy; BFS( aux ); } } } } int main() { cin>>n; cin>>x>>y; inicio.x = x; inicio.y = y; cin>>x>>y; fin.x = x; fin.y = y; dp[ inicio.x ][ inicio.y ] = 1; BFS(inicio); cout<< dp[fin.x][fin.y] <

I hope its not help that I'm wrong!!!
cronos
Topic archived. No new replies allowed.