0

Estoy teniendo una duda para un ejercicio de clase, el enunciado es el siguiente:

El problema a resolver consiste en encontrar un camino desde una posición (fila, columna) de la matriz, hasta una posición que contenga un valor máximo de la matriz sin que se descienda de valor durante el camino. La posición inicial se puede elegir al azar de entre las posiciones del borde. Ten en cuenta que puede darse el caso de que no sea posible encontrar un camino desde una posición inicial determinada. En este caso, simplemente se dice que no hay camino. La SOLUCIÓN debe ser RECURSIVA, y la solución encontrada por el algoritmo se debe escribir en la salida estándar como una secuencia de posiciones de la matriz junto con el valor que contiene.

El tema es el siguiente: a partir de una matriz dada hay que sacar el camino desde una posición al máximo de la matriz, siempre de forma ascendente. La matriz se rellena de forma aleatoria. Mi problema es que cuando llega a un punto en el que no puede subir, debe volver a la posición anterior y ver si existe un camino tomando otra de las posiciones posibles, hasta que vuelva a la posición inicial. Osea el método acaba cuando llega al máximo o vuelve a la primera posición (significando que ya ha comprobado todos los caminos posibles). Necesito ayuda para saber como hacer que vuelve atrás cuando se quede bloqueado. Tengo este código escrito:

//Metodo que busca el camino. Como parametros tiene la matriz sobre la que busca
// la i y la j que son las posiciones iniciales y el valor de la misma
public static void encontrarCamino(int[][] matriz, int i, int j, int valor, int valorAnterior){
    int maximo = obtenerMaximo(matriz); 
    //Va imprimiendo la secuencia de valores que sigue.
    System.out.println("(" + i + ", " + j + ") / " + valor);
    //Comprueba si puede moverse a cada una de las posiciones y si es asi se mueve a ella de forma recursiva.
    if( i - 1 >= 0 && j - 1 >= 0 &&  i - 1 < matriz.length && j - 1  < matriz[i].length && matriz[i - 1][j - 1] >= valor){
        encontrarCamino(matriz, i - 1, j - 1, matriz[i - 1][j - 1], valor);}

    else if( i - 1 >= 0 && j >= 0 &&  i - 1 < matriz.length && j < matriz[i].length && matriz[i - 1][j] >= valor ){
        encontrarCamino(matriz, i - 1, j, matriz[i - 1][j], valor);}    

    else if( i - 1 >= 0 && j + 1 >= 0 &&  i - 1 < matriz.length && j + 1 < matriz[i].length && matriz[i - 1][j + 1] >= valor){
        encontrarCamino(matriz, i - 1, j + 1, matriz[i - 1][j + 1], valor);}

    else if( i >= 0 && j - 1 >= 0 &&  i < matriz.length && j - 1 < matriz[i].length && matriz[i][j - 1] >= valor){
        encontrarCamino(matriz, i, j - 1, matriz[i][j - 1], valor);}

    else if( i >= 0 && j + 1 >= 0 &&  i < matriz.length && j + 1 < matriz[i].length && matriz[i][j + 1] >= valor){
        encontrarCamino(matriz, i, j + 1, matriz[i][j + 1], valor);}

    else if( i + 1 >= 0 && j - 1 >= 0 &&  i + 1 < matriz.length && j - 1 < matriz[i].length && matriz[i + 1][j - 1] >= valor){
        encontrarCamino(matriz, i + 1, j - 1, matriz[i + 1][j - 1], valor);}

    else if( i + 1 >= 0 && j >= 0 &&  i + 1 < matriz.length && j < matriz[i].length && matriz[i + 1][j] >= valor){
        encontrarCamino(matriz, i + 1, j, matriz[i + 1][j], valor);}

    else if( i + 1 >= 0 && j + 1 >= 0 &&  i + 1 < matriz.length && j + 1 < matriz[i].length && matriz[i + 1][j + 1] >= valor){
        encontrarCamino(matriz, i + 1, j + 1, matriz[i + 1][j + 1], valor);}

    else{
        if(valor == maximo){System.out.println("El ultimo valor es el maximo");}
        else{System.out.println("No es posible alcanzar el maximo");};
    }        

}

Los movimientos son en todas las posiciones de alrededor, incluido en diagonal. As funciona, pero no hace lo de volver, no explora todas las posibilidades, va elige uno y va subiendo todo lo que pueda. Debe ser todo recursivo.

Si alguien me ayudara a completar lo de volver estaría muy agradecido.

1 respuesta 1

1

Tenes que hacer que las posibilidades sean exploradas por lo que no tenes que usar if else porque esos significa que solo se va a tomar un camino (si se entra a un if los demás no se evalúan a causa del else), tenes que usar solo if hacer algo así:

public static void encontrarCamino(int[][] matriz, int i, int j, int valor, int valorAnterior){
    int maximo = obtenerMaximo(matriz); 
    //Va imprimiendo la secuencia de valores que sigue.
    System.out.println("(" + i + ", " + j + ") / " + valor);
    //Comprueba si puede moverse a cada una de las posiciones y si es asi se mueve a ella de forma recursiva.
    if( i - 1 >= 0 && j - 1 >= 0 &&  i - 1 < matriz.length && j - 1  < matriz[i].length && matriz[i - 1][j - 1] >= valor){
        encontrarCamino(matriz, i - 1, j - 1, matriz[i - 1][j - 1], valor);}

    if( i - 1 >= 0 && j >= 0 &&  i - 1 < matriz.length && j < matriz[i].length && matriz[i - 1][j] >= valor ){
        encontrarCamino(matriz, i - 1, j, matriz[i - 1][j], valor);}    

    if( i - 1 >= 0 && j + 1 >= 0 &&  i - 1 < matriz.length && j + 1 < matriz[i].length && matriz[i - 1][j + 1] >= valor){
        encontrarCamino(matriz, i - 1, j + 1, matriz[i - 1][j + 1], valor);}

    if( i >= 0 && j - 1 >= 0 &&  i < matriz.length && j - 1 < matriz[i].length && matriz[i][j - 1] >= valor){
        encontrarCamino(matriz, i, j - 1, matriz[i][j - 1], valor);}

    if( i >= 0 && j + 1 >= 0 &&  i < matriz.length && j + 1 < matriz[i].length && matriz[i][j + 1] >= valor){
        encontrarCamino(matriz, i, j + 1, matriz[i][j + 1], valor);}

    if( i + 1 >= 0 && j - 1 >= 0 &&  i + 1 < matriz.length && j - 1 < matriz[i].length && matriz[i + 1][j - 1] >= valor){
        encontrarCamino(matriz, i + 1, j - 1, matriz[i + 1][j - 1], valor);}

    if( i + 1 >= 0 && j >= 0 &&  i + 1 < matriz.length && j < matriz[i].length && matriz[i + 1][j] >= valor){
        encontrarCamino(matriz, i + 1, j, matriz[i + 1][j], valor);}

     if( i + 1 >= 0 && j + 1 >= 0 &&  i + 1 < matriz.length && j + 1 < matriz[i].length && matriz[i + 1][j + 1] >= valor){
        encontrarCamino(matriz, i + 1, j + 1, matriz[i + 1][j + 1], valor);}

     if(valor == maximo){
        System.out.println("El ultimo valor es el maximo");}
     else{
        System.out.println("No es posible alcanzar el maximo");
     }
}

Con esto es posible volver para atrás pero se esta perdiendo el saber si era posible alcanzar el mínimo o no (siempre diría que "El ultimo valor es el maximo" o que "No es posible alcanzar el maximo") . Para esto se puede usar un booleano hayCamino con valor inicial en false y que se haga true si hay por lo menos un camino quedando de la siguiente manera el código:

public static void encontrarCamino(int[][] matriz, int i, int j, int valor, int valorAnterior){
    int maximo = obtenerMaximo(matriz);
    boolean hayCamino = false; 
    //Va imprimiendo la secuencia de valores que sigue.
    System.out.println("(" + i + ", " + j + ") / " + valor);
    //Comprueba si puede moverse a cada una de las posiciones y si es asi se mueve a ella de forma recursiva.
    if( i - 1 >= 0 && j - 1 >= 0 &&  i - 1 < matriz.length && j - 1  < matriz[i].length && matriz[i - 1][j - 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i - 1, j - 1, matriz[i - 1][j - 1], valor);}

    if( i - 1 >= 0 && j >= 0 &&  i - 1 < matriz.length && j < matriz[i].length && matriz[i - 1][j] >= valor ){
        hayCamino = true;
        encontrarCamino(matriz, i - 1, j, matriz[i - 1][j], valor);}    

    if( i - 1 >= 0 && j + 1 >= 0 &&  i - 1 < matriz.length && j + 1 < matriz[i].length && matriz[i - 1][j + 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i - 1, j + 1, matriz[i - 1][j + 1], valor);}

    if( i >= 0 && j - 1 >= 0 &&  i < matriz.length && j - 1 < matriz[i].length && matriz[i][j - 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i, j - 1, matriz[i][j - 1], valor);}

    if( i >= 0 && j + 1 >= 0 &&  i < matriz.length && j + 1 < matriz[i].length && matriz[i][j + 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i, j + 1, matriz[i][j + 1], valor);}

    if( i + 1 >= 0 && j - 1 >= 0 &&  i + 1 < matriz.length && j - 1 < matriz[i].length && matriz[i + 1][j - 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i + 1, j - 1, matriz[i + 1][j - 1], valor);}

    if( i + 1 >= 0 && j >= 0 &&  i + 1 < matriz.length && j < matriz[i].length && matriz[i + 1][j] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i + 1, j, matriz[i + 1][j], valor);}

     if( i + 1 >= 0 && j + 1 >= 0 &&  i + 1 < matriz.length && j + 1 < matriz[i].length && matriz[i + 1][j + 1] >= valor){
        hayCamino = true;
        encontrarCamino(matriz, i + 1, j + 1, matriz[i + 1][j + 1], valor);}
     if(!hayCamino){
        if(valor == maximo){
          System.out.println("El ultimo valor es el maximo");}
       else{
          System.out.println("No es posible alcanzar el maximo");
       }
     }   
}

Nota:

  1. Al estarse comprobando todos los caminos posibles se van a imprir varios "El ultimo valor es el maximo" o "No es posible alcanzar el maximo" debido a si hayCamino = false se va a imprimir una cosa o la otra y hayCamino va a ser false siempre que un camino sea final (no haya mas lugar a donde ir o se llego al maximo) y esto va suceder mucho. Para cambiar este comportamineto se deberia cambiar la firma del método.

  2. Con esto no es posible indicar correctamente en la salida estándar como una secuencia de posiciones de la matriz junto con el valor que contiene solo si se encontró un camino o no para esto se debería también cambiar la firma del método.

1
  • Buenas. Muchas gracias me has ayudado mucho. Con tus cambios ya va bien, y si que vuelve a recorrer todas las posiciones. La único que me queda es que cuando no haya camino al maximo muestre "No hay camino" pero que cuando haya un camino posible muestre la secuencia de movimientos. He leido tus notas pero no consigo terminar con eso,¿Sabrias como es? el 24 feb. 2019 a las 12:43

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.