Блог

Я работал над проблемой Rat Maze (вы можете перемещаться вправо или вниз, если 1, и не куда, если 0). У меня были проблемы с тем, что мой результат не возвращался в стек, я проследил его, и все казалось нормальным, затем я изменил свой код, и это сработало, и я не понимал, почему моя трассировка неверна.

Я опубликую 3 версии кода, сначала правильную, затем 2 неправильные. Мой вопрос заключается в том, какова правильная трассировка каждого рекурсивного кода, чтобы я мог в следующий раз правильно отслеживать свой собственный код и понимать, что я правильно отслеживаю его, чтобы найти ошибку.

Я должен упомянуть, что результатом является количество возможных путей для достижения [n-1] [m-1]

Правильный код

  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 amp;amp; row == arr.length-1){
  System.out.println("Result: "  result);
   return result 1;
}

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

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


return resu<    
  }
  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));         
  }
}
  

Неверный код 1
Результат всегда будет равен 0 в стеке вызовов, даже после обновления в базовом варианте
Я просто избавился от ‘result =’ в рекурсивных случаях

 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 amp;amp; row == arr.length-1){
  System.out.println("Result: "  result);
   return result 1;
}

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

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

  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));         
 }
}
  

Неверный код 2
В базовом случае я избавился от return и вместо этого использую return = 1,
в стеке первого вызова это значение равно 1, но по мере продвижения вверх по стеку оно возвращается к значению 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 amp;amp; row == arr.length-1){
  System.out.println("Result: "  result);
   result =1;
}

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

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

  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));         
 }
}
  

Дополнительная правка
Переход ко второму некорректному коду, если я добавлю return = в рекурсивных случаях, но не в базовом, код все равно будет выглядеть нормально
импорт java.io .; импортируйте 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 amp;amp; row == arr.length-1){
  System.out.println("Result: "  result);
   result =1;
}

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

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

  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));         
 }
}
  

Ах, классическая ошибка. Вы забыли вернуть свой результат из условий if.

У вас есть это :

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

Чего вы хотите, так это:

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