Hola amigos, tengo un problema al implementar una version recursiva de un algoritmo que he realizado, me da valores distintos, espero que puedan ayudarme, aca les dejo el codigo de forma Iterativa ( OK ) y el codigo de forma Recursiva que no esta OK.
Los juegos de datos no dan iguales:
El algoritmo trata de dada 2 posiciones de origen y destino en un tablero, buscar la cantidad de caminos entre ellos.
espero su ayuda no se en que me equivoco
Algoritmo Iterativo (OK)
Código:
#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;
}
Algoritmo Recursivo mal
Código:
#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;
}
saludos
cronos