C++

Forum

 
Problem in Algorithm Recursive?

cronopio (95)
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 ) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>

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] <<endl;
    system("pause");
    return 0;
}


Recursive Algorithm ( not OK ) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <stack>
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] <<endl; 
    system("pause");
    return 0;
}


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