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.