在我的腦海裏發現很難想到回溯，我能得到一些幫助嗎？

Question

我的問題是。我寫了一個代碼。我的輸出是false而不是true。我嘗試了所有我能想到的解決方案。我需要一些幫助 。 我剛完成遞歸課程。 我完成了材料。我使用遞歸編寫了一些程序，並且我做得很好。 我有回溯問題。例如，這一個。 我需要從開始[0] [0] 到達[n-1] [n-1]的位置，我不能使用穿過對角線，只能上，下，左，右。 該路徑需要處於以下模式 - 如果下一個索引大於其中的一個索引，則指向他之前的索引。 我試圖寫代碼。它應該返回true，但它返回false。 也是這張圖片的唯一例子。它應該在任何n * n陣列上工作 圖片： ！ find a path from (0,0) until [n-1][n-1]

public class Backtrack 
{ 

    public static boolean isPath(int [][] arr) 
    { 
     return isPath(arr ,0 ,0, 0 ,0); 
    } 

    //checks that i'm not out of bounceof the array 
    private static boolean isSafe(int[][] arr, int row, int col, int x,int y) { 
     if(x >= 0 && x < arr[0].length && y >= 0 && y < arr.length && 
     row >= 0 && col >= 0 && row < arr.length && col < arr[0].length) 
      return true; 

    return false; 
    } 
    //checks the path 
    private static boolean isPath (int [][] arr, int row, int col,int x,int y) 
    { 
     //if next index is not 1 larger then the previous one @return false 
     if (arr[row][x]!= arr[y][col] + 1) 
      return false; 
     //if arrived to arr[n-1][n-1] position.then the path was found. @return  true goal achived 
     if (row==arr.length-1 && col==arr.length-1) 
      return true; 
     if(isSafe(arr, row, col, x, y) == true) { 

      if(isPath(arr,row, col, ++x, y) == true) 
       return true; 
      if(isPath(arr, row, col, x , ++y) == true) 
       return true; 

     return false; 
     } 
    return false; 
    } 
} 

Answer 1

一些初步的問題，我發現：

• 你是在混淆參數。從外觀上看，你希望arr[row][col]引用前一個空格，並且arr[x][y]成爲下一個空格。
• 您檢查當前平方與前一平方是否正確關聯。從理論上講，這是有效的，但是當你從當前和以前（即return isPath(arr ,0 ,0, 0 ,0);）傳遞相同的值開始時就失敗了。
• 你檢查當前值是否正常，當你應該檢查新值是否是。 if(isSafe(arr, row, col, x, y) == true) {應該是if(isSafe(arr, row, col, x+1, y) == true) {和類似的四個其他方向，你可以去。
• 當你剛剛加1時，你正在遞增x和y。if(isPath(arr,row, col, x+1, y) == true)。你擁有它的方式，你會沿對角線走。
• 你不覆蓋向上和向左的方向。

希望這會有所幫助。