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.

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.