Java, recherche de récursion sur le labyrinthe de rats

Question

Je travaillais sur le problème du labyrinthe de rat (vous pouvez vous déplacer vers la droite ou vers le bas si 1, et non si 0). J'ai eu des problèmes que mon résultat ne renverrait pas la pile, je l'ai tracé et tout a semblé bien, alors j'ai changé mon code et cela a fonctionné et je ne comprenais pas comment ma trace est incorrecte.

Je posterai 3 versions du code, d'abord correct puis 2 incorrectes. Ma question concerne la bonne trace de chaque code récursif afin que je puisse, la prochaine fois, tracer correctement mon propre code et comprendre que je le parcoure correctement pour trouver une erreur.

Je dois mentionner résultat est le nombre de chemins possibles pour atteindre [n-1] [m-1]

code correct

import java.io.*; 
import java.util.*; 

class Solution { 
public static int findpath(int [][] arr){ 
    int row = 0; 
    int col = 0; 
    int result = 0; 
    return findpathHelper(arr, row, col, result); 

} 

public static int findpathHelper(int [][] arr, int row, int col, int result){ 

System.out.println(row); 
System.out.println(col); 
System.out.println(); 

if(col == arr[row].length-1 && row == arr.length-1){ 
    System.out.println("Result: " +result); 
    return result+1; 
} 

if(row+1 != arr.length && arr[row+1][col] != 0){  
    result = findpathHelper(arr, row+1, col, result); 
} 

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    result = findpathHelper(arr, row,col+1, result); 
} 


return result;  
    } 
    public static void main(String[] args) { 
    int [][] path = {{1,1,1,1}, 
       {0,1,1,1}, 
       {1,0,0,1}, 
       {1,1,1,1}}; 

    System.out.println(findpath(path));   
    } 
} 

code incorrect 1 Le résultat sera toujours 0 jusqu'à la pile d'appels, même après avoir été mis à jour dans le cas de base Je me suis simplement débarrassé de 'result =' dans les cas récursifs

import java.io.*; 
import java.util.*; 



class Solution { 
    public static int findpath(int [][] arr){ 
    int row = 0; 
    int col = 0; 
    int result = 0; 
    return findpathHelper(arr, row, col, result); 

} 

public static int findpathHelper(int [][] arr, int row, int col, int result){ 

System.out.println(row); 
System.out.println(col); 
System.out.println(); 

if(col == arr[row].length-1 && row == arr.length-1){ 
    System.out.println("Result: " +result); 
    return result+1; 
} 

if(row+1 != arr.length && arr[row+1][col] != 0){  
    findpathHelper(arr, row+1, col, result); 
} 

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    findpathHelper(arr, row,col+1, result); 
} 
return result;  
} 

    public static void main(String[] args) { 
    int [][] path = {{1,1,1,1}, 
       {0,1,1,1}, 
       {1,0,0,1}, 
       {1,1,1,1}}; 

    System.out.println(findpath(path));   
} 
} 

code incorrect 2 En cas de base, je me suis débarrassé de retour et à la place je utilise le retour + = 1, dans la première pile d'appel est 1 mais comme il remonte la pile revient à étant 0.

import java.io.*; 
import java.util.*; 



class Solution { 
    public static int findpath(int [][] arr){ 
    int row = 0; 
    int col = 0; 
    int result = 0; 
    return findpathHelper(arr, row, col, result); 

} 

public static int findpathHelper(int [][] arr, int row, int col, int result){ 

System.out.println(row); 
System.out.println(col); 
System.out.println(); 

if(col == arr[row].length-1 && row == arr.length-1){ 
    System.out.println("Result: " +result); 
    result+=1; 
} 

if(row+1 != arr.length && arr[row+1][col] != 0){  
    return = findpathHelper(arr, row+1, col, result); 
} 

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    return = findpathHelper(arr, row,col+1, result); 
} 
return result;  
} 

    public static void main(String[] args) { 
    int [][] path = {{1,1,1,1}, 
       {0,1,1,1}, 
       {1,0,0,1}, 
       {1,1,1,1}}; 

    System.out.println(findpath(path));   
} 
} 

additionnelle Modifier allant du 2ème code incorrect, si j'ajoute le retour = sur th e cas récursifs mais pas le cas de base le code semble toujours correct import java.io. ; import java.util.;

class Solution { 
    public static int findpath(int [][] arr){ 
    int row = 0; 
    int col = 0; 
    int result = 0; 
    return findpathHelper(arr, row, col, result); 

} 

public static int findpathHelper(int [][] arr, int row, int col, int result){ 

System.out.println(row); 
System.out.println(col); 
System.out.println(); 

if(col == arr[row].length-1 && row == arr.length-1){ 
    System.out.println("Result: " +result); 
    result+=1; 
} 

if(row+1 != arr.length && arr[row+1][col] != 0){  
    result = findpathHelper(arr, row+1, col, result); 
} 

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    result = findpathHelper(arr, row,col+1, result); 
} 
return result;  
} 

    public static void main(String[] args) { 
    int [][] path = {{1,1,1,1}, 
       {0,1,1,1}, 
       {1,0,0,1}, 
       {1,1,1,1}}; 

    System.out.println(findpath(path));   
} 
} 

Answer 1

Ah l'erreur classique. Vous avez oublié de renvoyer votre résultat à l'intérieur des conditions if.

Vous avez ceci:

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    findpathHelper(arr, row,col+1, result); 
} 

Ce que vous voulez est ceci:

if(col+1 != arr[row].length && arr[row][col+1] != 0){  
    return findpathHelper(arr, row,col+1, result); 
}