簡單的DFS遍歷的停止條件

作爲一種實踐，我試圖解決這個problem on topcoder，我試着爲它實現DFS解決方案，除了一個bug之外它運行良好：即使它到達死衚衕，它仍然遍歷每個未訪問的單元中，初始碼是：簡單的DFS遍歷的停止條件

public void func(int[][] x, StringBuilder s, int i, int j, int n) { 
    if (i < 0 || j < 0 || i > n || j > n || x[i][j] == 1) { 
     return; 
    } 
    s.append((char) (97 + j)); 
    s.append(n - i + 1 + "-"); 
    x[i][j] = 1; 
    func(x, s, i, j + 1, n); 
    func(x, s, i - 1, j, n); 
    func(x, s, i + 1, j, n); 
    func(x, s, i, j - 1, n); 
    return; 
} 

public String dukePath(int n, String initPosition) { 
    String p = initPosition; 
    int x[][] = new int[n][n]; 
    StringBuilder s = new StringBuilder(""); 
    func(x, s, n - Integer.parseInt(p.charAt(1) + ""), (int) p.charAt(0) - 97, n - 1); 
    s.replace(s.length() - 1, s.length(), ""); 
    if (s.length() > 40) { 
     s.replace(20, s.length() - 20, "..."); 
    } 
    return s.toString(); 
}

所以我嘗試通過添加一個布爾標誌，及初始位置（Z，Y）與當前小區比較來修改函數「FUNC（）」的簽名;如果代碼嘗試重新訪問初始位置，則應該返回，但它也不起作用。

如何在再次達到死角或初始位置時停止遍歷？

來源

2012-08-22 a.u.r

你標記'X [i] [j] = 1;'當你達到一個死結束，但是當你回溯時，你並沒有將它標記爲未訪問過'x [i] [j] = 0;'。 – irrelephant

我只想當它到達死衚衕時停下來，不去探索另一個單元格，所以不需要回溯我猜 –

嘗試沒有StringBuilder並傳遞常規字符串。您可能還需要返回String。 – irrelephant

您正在錯誤地處理這個問題，您只需要在每一步移動到詞典上最大的鄰居，直到您到達您訪問過所有相鄰單元的點。這是簡單的迭代，並且不需要DFS：

public static String dukePath(int n, String initPosition) { 
    int x = initPosition.charAt(0) - 'a'; 
    int y = n - (initPosition.charAt(1) - '0'); 
    boolean grid[][] = new boolean[n][n]; 
    StringBuilder s = new StringBuilder(initPosition); 

    while (true) { 
     grid[x][y] = true; 

     if (x < (n - 1) && !grid[x + 1][y]) 
      x++; // Right 
     else if (y > 0 && !grid[x][y - 1]) 
      y--; // Up 
     else if (y < (n - 1) && !grid[x][y + 1]) 
      y++; // Down 
     else if (x > 0 && !grid[x - 1][y]) 
      x--; // Left 
     else 
      break; // Nowhere left to go! 

     s.append("-" + (char)('a' + x) + (char)('0' + n - y)); 
    } 

    if (s.length() > 40) { 
     s.replace(20, s.length() - 20, "..."); 
    } 

    return s.toString(); 
} 

public static void main(String args[]) 
{ 
    System.out.println(dukePath(3, "b2")); 
    System.out.println(dukePath(4, "d4")); 
    System.out.println(dukePath(3, "a2")); 
    System.out.println(dukePath(4, "d3")); 
    System.out.println(dukePath(8, "a8")); 
}

給出了預期的效果：

b2-c2-c3-b3-a3-a2-a1-b1-c1 
d4-d3-d2-d1-c1-c2-c3...b3-b2-b1-a1-a2-a3-a4 
a2-b2-c2-c3-b3-a3 
d3-d4-c4-c3-c2-d2-d1...b2-b3-b4-a4-a3-a2-a1 
a8-b8-c8-d8-e8-f8-g8...a1-a2-a3-a4-a5-a6-a7

來源

2012-08-22 09:51:47 verdesmarald

我以前就知道迭代解決方案，但我試圖用DFS實現它。正如你可以看到我的做法是相同的：贊成正確的方向，然後等，等.. 我所做的只是交換X和YS。也許我沒有澄清我的問題：的第三個例子，我的代碼返回： A2-B2-C2-C3-B3-A3-C1-B1-A1而不是A2-B2-C2-C3- b3-a3多餘的單元格「c1 -b1-a1」 –

@aur這就是DFS的工作原理。一旦它達到不能再繼續的程度，它就會回到可能的程度。 DFS不是爲了阻止第一次遇到終端節點而設計的，您可以對其進行修改以便它能夠做到，但是到底是什麼？你只是添加一堆沒有任何作用的代碼。 – verdesmarald

@verdesmarald我相信你是對的，現在我明白了。另一個問題：如果我有一個目標單元格，那麼當我到達該單元格時，我怎麼能終止代碼？ –

我認爲最簡單的解決方案是創建一個包含i和j的對象集合。在func的每次調用中，如果該集合包含i和j的目標對象，則不應調用func函數。這種方法既包括後退和循環。

來源

2012-08-22 08:30:40

我試圖通過添加初始位置作爲參數，並比較當前單元格;以決定是否停止，但它沒有工作： public void func（int [] [] x，StringBuilder s，int i，int j，int n，boolean f，int z，int y）{ // z＆y是在問題中給出的初始座標，如果（i == z && j == y && x [z] [y] == 1） \t \t \t f = true; \t \t if（f == true） \t \t \t return; //其餘代碼如上 –

這不起作用，因爲您的程序可能會落入xy空間中不包含原始位置的循環中。一般來說，當你四次調用這些func函數時，你需要檢查目標位置是否以前沒有被看到過。 –

不，即使當它到達初始位置並將布爾值「f」更改爲true時，它也不起作用 –

簡單的DFS遍歷的停止條件

回答

相關問題