Buenas,
les cuento q estoy aprendiendo la tecnica del backtracking y me he encontrado q no es tan simple como parecia jeje. Cualquier material que sepan pueda ubicar por Internet seria util, he dado vueltas pero hay pocos 'buenos' ejemplos.
Un problema q no he podido resolver seria el sig.
Supongan q tengo la sig matriz:
Mapa m = {
{1,1,1,1,1},
{0,1,1,0,1},
{0,0,1,0,1},
{0,0,1,0,1},
{0,0,1,0,1}};
suponiendo que los unos fueran tierra y los ceros agua, se me pide devolver la longitud del camino mas corto entre 2 puntos. Los movimientos posibles son arriba, abajo, izquierda, derecha, no se permite mover oblicuamente. Se pide q utilice backtracking y que devuelva -1 en el caso que no exista un camino posible.
La firma de la funcion seria algo asi:
int longitudCaminoMasCorto(Mapa m, int n, int i1, int j1, int i2, int j2);
En el ejemplo si llamo a la funcion asi:
long = longitudCaminoMasCorto(m,0,0,0,4,4)
Le estoy pidiendo q me devuelva el camino mas corto entre la esq superior izquierda (0,0) y la esquina inferior derecha (4,4). Me tendria q devolver 9.
cuando hay 2 caminos posibles, como puedo luego discernir cual es el correcto? y segun el codigo que hice hasta ahora y que dejo mas abajo no puedo devolver -1.
alguna ayuda??
/*CODIGO*/
int longitudCaminoMasCorto(Mapa m, int n, int i1, int j1, int i2, int j2){
//Arrays de adiciones de X e Y al moverme por el mapa.
int X[4] = {1,0,-1,0};
int Y[4] = {0,-1,0,1};
//Si pertenece al mapa ...
if(perteneceAlMapa(i1,j1)){
//si es tierra...
if(m[i1][j1] == 1){
//marco como visitada.
m[i1][j1] = 2;
//agrego 1 a la longitud del camino
n += 1;
//es el destino?
if((i1 == i2) && (j1 == j2)){
//devuelvo n.
return n;
//de lo contrario pregunto por CADA UNA de las alternativas...
}else{
//si la alternativa pertenece al mapa y no la visite
//llamo a esta funcion desde la posicion alternativa
if((perteneceAlMapa(i1+X[0],j1+Y[0])) && (m[i1+X[0]][j1+Y[0]] != 2)){
n = longitudCaminoMasCorto(m, n, i1+X[0], j1+Y[0], i2, j2);
};
if((perteneceAlMapa(i1+X[1],j1+Y[1])) && (m[i1+X[1]][j1+Y[1]] != 2)){
n = longitudCaminoMasCorto(m, n, i1+X[1], j1+Y[1], i2, j2);
};
if((perteneceAlMapa(i1+X[2],j1+Y[2])) && (m[i1+X[2]][j1+Y[2]] != 2)){
n = longitudCaminoMasCorto(m, n, i1+X[2], j1+Y[2], i2, j2);
};
if((perteneceAlMapa(i1+X[3],j1+Y[3])) && (m[i1+X[3]][j1+Y[3]] != 2)){
n = longitudCaminoMasCorto(m, n, i1+X[3], j1+Y[3], i2, j2);
};
}
}
}
return n;
}
/*FIN CODIGO*/
