遞歸路徑發現問題

Question

我正在編寫一個路徑查找算法，我需要一些幫助來找出如何通過避免遞歸進行而非常快速創建異常情況。

我有1個矩陣（spaces = walls; hash = blocs; 2 =實際位置） 「2」需要收集所有的「＃」，每次他走到一個「＃」它消失。

我自願產生了一個不可能解釋我的問題。

{ , , , , , , , }; 
{ , #, #, #, #, #, #, }; 
{ , #, , , , , #, }; 
{ , #, , #, #, , #, }; 
{ , #, , #, #, , #, }; 
{ , #, , #, #, , #, }; 
{ , #, , #, #, , #, }; 
{ , #, , , , , #, }; 
{ , #, #, #, 2, #, #, }; 
{ , , , , , , , }; 

正如您所看到的，地圖中間有一個無法到達的島嶼。

我想如果你們有任何想法如何檢測這種情況。我無法想出任何辦法。

我的繼承人的實際代碼：

檢查一些例外情況，並返回true或false：

static bool BreakCaseFound() { 
    int EndCases = 0; // 3 blocs with 3 empty slots around 
    bool BreakCases = false; // 1 bloc with 4 empty slots around 
    int temp = 0; 
    for(int i = 1; i<17; i++) { 
     for(int j = 1; j<17; j++) { 
      if(matrice[j, i] == bloc) { 
       if (matrice[j+1, i] == empty) { 
        temp++; 
       } 
       if (matrice[j-1, i] == empty) { 
        temp++; 
       } 
       if (matrice[j, i+1] == empty) { 
        temp++; 
       } 
       if (matrice[j, i-1] == empty) { 
        temp++; 
       } 
      } 
      switch(temp) { 
       case 3: 
        EndCases++; 
        temp = 0; 
        break; 
       case 4: 
        temp = 0; 
        BreakCases = true; 
        break; 
       default: 
        temp = 0; 
        break; 
      } 

      if(BreakCases || EndCases >= 3) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

我型我秀功能（MS-DOS窗口）

static void show() { 
    Console.Clear(); 
    for(int i =0; i<18; i++) { 
     for(int j = 0; j<18; j++) { 
      if(matrice[j,i] == empty) { 
       Console.Write(" "); 
      } 
      else { 
       if (matrice[j, i] == 2) { matrice[j, i] = bloc ; } 
       if (matrice[j, i] == 3) { matrice[j, i] = 5 ; } 
       Console.Write(matrice[j, i]); 
      } 
     } 
     Console.Write("\n"); 
    } 
} 

我的算法：

static dynamic move(int actualPosCol, int actualPosLigne, List<int[]> path, List<int[]> RealPath) 
{ 
    matrice[path[path.Count()-1][0], path[path.Count()-1][1]] = 5; 
    show(); 
    if(nbBlocs > 0) { 
     show(); 

     //Left move 
     if((matrice[path[path.Count() - 1][0]-1, path[path.Count() - 1][1]] == bloc) 
     && (!BreakCaseFound())) { 
      nbBlocs--; 
      matrice[actualPosCol, actualPosLigne] = empty; 
      int[] posNext = new int[2] {actualPosCol-1, actualPosLigne}; 
      path.Add(posNext); 
      move(actualPosCol-1, actualPosLigne, path, RealPath); 
     } 
     //Right move 
     if((matrice[path[path.Count() - 1][0]+1, path[path.Count() - 1][1]] == bloc) 
     && (!BreakCaseFound())) { 
      nbBlocs--; 
      matrice[actualPosCol, actualPosLigne] = empty; 
      int[] posNext = new int[2] {actualPosCol+1, actualPosLigne}; 
      path.Add(posNext); 
      move(actualPosCol+1, actualPosLigne, path, RealPath); 

     } 

     //Down move 
     if ((matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]+1] == bloc) 
     && (!BreakCaseFound())) { 
      nbBlocs--; 
      matrice[actualPosCol, actualPosLigne] = empty; 
      int[] posNext = new int[2] {actualPosCol, actualPosLigne+1}; 
      path.Add(posNext); 
      move(actualPosCol, actualPosLigne+1, path, RealPath); 
     } 
     //Up move 
     if ((matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]-1] == bloc) 
     && (!BreakCaseFound())) { 
      nbBlocs--; 
      matrice[actualPosCol, actualPosLigne] = empty; 
      int[] posNext = new int[2] {actualPosCol, actualPosLigne-1}; 
      path.Add(posNext); 
      move(actualPosCol, actualPosLigne-1, path, RealPath); 
     } 

     if(nbBlocs > 0) { 
      //Can't move right, left, up or down 
      matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]] = 3; 
      show(); 
      path.Remove(path.Last()); //remove last move from the List 
      nbBlocs++; 
     } 

     return path; 
    } 
    else { //No more blocs, path found. 
     foreach(int[] way in path) { 
      if(!RealPath.Contains(way)) { 
       RealPath.Add(way); 
      } 
     } 
     return path; 
    } 
} 

Answer 1

也許我瘋了，但每次看到涉及斷開連續區域的問題時，我都認爲disjoint sets。不相交集是爲非常高效的合併而設計的集合，如果您試圖查找＃是否連接了許多區域，則合併是您做了很多工作。

將您地圖上的每個位置放入其自己的不相交集。任何包含位置的集合最終都將包含您可以從中移動到的所有位置。怎麼樣？我們繞着地圖走，任何時候我們可以從一個地方移動到另一個地方，我們合併套。

按照什麼順序進行這些步驟？從某個地方填充你的整個地圖 - 從每個位置到任何你不是來自鄰居的鄰居進行填充。如果X與Y相同，那麼從點X到點Y的填充不應該做任何事情，否則，如果可以在它們之間移動，則應該合併X和Y的集合。如果以前從未訪問過Y，那麼從Y開始遞歸。

該解決方案將針對地圖中的n個位置在O（n inverse-ackermann（n））中運行。