Ver Mensaje Individual
  #1 (permalink)  
Antiguo 17/05/2013, 07:40
mariamgn
 
Fecha de Ingreso: noviembre-2012
Mensajes: 12
Antigüedad: 12 años
Puntos: 0
Pregunta Problema en algoritmo recursivo!!!

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