Dificultad para escribir una solución recursiva al problema de "Rata en un laberinto"

Mi pregunta es esencialmente una duda sobre la recursividad. Estaba resolviendo el clásico problema transversal DFS "Rata en un laberinto". Mi entrada fue una n*n intmatriz a[][]donde para índices iy j, a[i][j]podría ser 0o 1. 0significaba que la rata hipotética no podía visitar el elemento y que 1sí podía. La rata solo podía ir hacia abajo ( "D") o hacia la derecha ( "R"). La tarea consistía en generar todos los movimientos. Cadenas como RDRDRDesa representaban el movimiento de la rata a través del laberinto. La rata comienza a[0][0]y debe llegar a[n-1][n-1]. La entrada fue el laberinto en sí.

Escribí el siguiente código

 public boolean isSafe(int x, int y, int[][] a, int n)
 {
    if(x >= 0 && x < n && y >= 0 && y < n && a[x][y] == 1)
        return true;
    else
        return false;
 }
 public ArrayList<String> printPath(int[][] a, int n)
 {
     ArrayList<String> res = new ArrayList<String>();
     solve(0,0,new String(), res,a,n);
     return res;
 }
 public void solve(int x, int y, String sol, ArrayList<String> res , 
 int[][]a, int n)
 {
     if(x == n-1 && y == n-1)
     {
         res.add(sol);
         return;
     }
     y++;
     if(isSafe(x,y,a,n))
     {
         solve(x,y,sol + "R",res,a,n);
     }
     else 
         y--;
     x++;
     if(isSafe(x,y,a,n))
     {
         solve(x,y,sol+"D",res,a,n);
     }
     else
         x--;
 }`

donde isSafecomprobar si se permite un movimiento, printPathes una función auxiliar para imprimir la salida y solvees la función recursiva utilizada para atravesar el laberinto. arepresenta la matriz del laberinto como una matriz 2D. Para la entrada

{1 0 0 0 
 1 1 0 1 
 0 1 0 0 
 0 1 1 1}

Me sale el siguiente resultado

DRDDRR DDDRR

Obviamente, la segunda cadena representa un resultado incorrecto.

Sin embargo, cuando cambié la solvefunción así

public void solve(int x, int y, String sol, ArrayList<String> res, 
int[][]a, int n)
 {
    if(x == n-1 && y == n-1)
    {
        res.add(sol);
        return;
    }
    if(!isSafe(x,y,a,n))
       return;
    solve(x+1,y,sol + "D",res,a,n);
    solve(x,y+1,sol + "R",res,a,n);    
    return;  
 }

Me sale la salida correcta. Lo que no entiendo es lo que resultó en la salida incorrecta en mi solución anterior, ya que para mí las dos soluciones son lógicamente similares. Sé que es una lectura larga, pero cualquier idea sería muy apreciada.

Respuesta 1

En la primera solución, el incremento de la variable y++solo se deshace si la llamada al isSafevalor incrementado vuelve negativa y se transfiere a la comprobación de xsi era cierto. Esto significa que la verificación hacia abajo en un campo que tiene un vecino válido a la derecha, en particular el campo [1] [0], se realizará con el valor incrementado de en ylugar del correcto.

Si modifica la primera solución como esta

y++;
if(isSafe(x,y,a,n)){
    solve(x,y,sol + "R",res,a,n);
}
y--;

la primera solución funcionará correctamente al igual que la segunda. En la segunda solución, el incremento solo se realiza en el argumento de la función, no en una variable local.

Respuesta: 2

Tengo un archivo xml creado con xmloutputter. En la primera vez que se crea, me crea el encabezado, pero luego agrego información, no lo haría. ¿Cómo puedo omitirlo? EDITAR elemento ...

Estoy ejecutando los códigos oficiales de SDK Junit, y funciona bien. Pero cuando cambio la información de la cuenta a la mía, se produce una excepción. Debug dice que devuelve el estado http de 400 cuando se publica en el punto final "/ oauth / ...

Me voy a conectar a un servicio web que tiene un WSDL que se dice que es compatible con JAX WS 2.0 / 2.1. Qué significa eso? ¿Tendrá algún impacto en la forma en que me conecto al servicio web? Que cierto ...

Muy nuevo en Java y Oop en general. así que sé amable. Tengo un archivo de texto que contiene 10 enteros, searchkeysArray.txt. El programa crea una matriz llamada keysArr. Tengo otro archivo de texto de 500 ...