Java：麻煩隨機DFS運行建立迷宮

我有麻煩隨機訪問從一個節點到它的鄰居，很少是整個圖（一個MxN數組，在這個測試4x4）訪問，我沒有得到我在這裏做錯了。Java：麻煩隨機DFS運行建立迷宮

import java.util.ArrayList; 



class IJ { 

    int i; 
    int j; 

    IJ (int i,int j){ 
     i = this.i; 
     j= this.j; 

    } 

} 


class Graph { 

    int M; 
    int N; 

    int adjacencyMatrix[][]; 

    ArrayList <IJ> orderOfVisits; 

    Graph(int M,int N){ 

     this.M=M; 
     this.N=N; 
     adjacencyMatrix=new int[M][N]; 

     for (int i=0; i<M; i++) 
      for (int j=0;j<N;j++){ 
        adjacencyMatrix[i][j]=-1; //mark all vertices as not visited 
      } 

     orderOfVisits = new ArrayList<IJ>(); 

    } 

String northOrEast() { 

     double lottery = Math.random(); 

     if (lottery>0.5D) {return "north";} 

     else {return "south";} 


    } 

String southOrEastOrNorth() { 

    double lottery=Math.random(); 

    if (lottery<=0.33D){ 
     return "south"; 
    } 

    else if ((lottery > 0.33D) && (lottery <= 0.66D)) { 
     return "east"; 
    } 

    else if(lottery > 0.66D) 
    { 
     return "north"; 
    } 

    System.out.println("method sEn has returned null "); 
    return null; 
} 


String southOrEast(){ 

    double lottery = Math.random(); 

     if (lottery>0.5D) {return "south";} 

     else {return "east";} 


} 

String southOrEastOrWest() { 

    double lottery=Math.random(); 

    if (lottery<=0.33D){ 
     return "south"; 
    } 

    else if ((lottery > 0.33D) && (lottery <= 0.66D)) { 
     return "east"; 
    } 

    else if(lottery > 0.66D) 
    { 
     return "west"; 
    } 

    System.out.println("method sEw has returned null "); 
    return null; 

} 

String southOrWest(){ 

    double lottery = Math.random(); 

     if (lottery>0.5D) {return "south";} 

     else {return "west";} 


} 

String southOrNorthOrWest() { 

    double lottery=Math.random(); 

    if (lottery<=0.33D){ 
     return "south"; 
    } 

    else if ((lottery > 0.33D) && (lottery <= 0.66D)) { 
     return "north"; 
    } 

    else if(lottery > 0.66D) 
    { 
     return "west"; 
    } 

    System.out.println("method sNw has returned null "); 
    return null; 

} 

String northOrWest(){ 

    double lottery = Math.random(); 

     if (lottery>0.5D) {return "north";} 

     else {return "west";} 


} 

String eastOrNorthOrWest() { 

    double lottery=Math.random(); 

    if (lottery<=0.33D){ 
     return "east"; 
    } 

    else if ((lottery > 0.33D) && (lottery <= 0.66D)) { 
     return "north"; 
    } 

    else if(lottery > 0.66D) 
    { 
     return "west"; 
    } 

    System.out.println("method eNw has returned null "); 
    return null; 

} 

String any() { 

    double lottery=Math.random(); 

    if (lottery<=0.25D){ 
     return "east"; 
    } 

    else if ((lottery > 0.25D) && (lottery <= 0.50D)) { 
     return "north"; 
    } 

    else if ((lottery > 0.5D) && (lottery <= 0.75D)) { 
     return "south"; 
    } 

    else if(lottery > 0.75D) 
    { 
     return "west"; 
    } 

    System.out.println("method any has returned null "); 
    return null; 

} 



String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid, int i, int j){ 

    //border cases 

    //left lower corner, only north and east are valid 
    if ((northValid==true) && (southValid==false) &&(eastValid==true) && (westValid==false)) 
    {return northOrEast();} 

     //left border: 
    if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==false)) 
    {return southOrEastOrNorth();} 

    //upper left corner, only south and east are valid 
    if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==false)) 
    {return southOrEast();} 


     //upper border 
    if ((northValid==false) && (southValid==true) && (eastValid==true) && (westValid==true)) 
    {return southOrEastOrWest();} 

     //upper right corner 
    if ((northValid==false) && (southValid==true) && (eastValid==false) && (westValid==true)) 
    {return southOrWest();} 

    //right border 
    if ((northValid==true) && (southValid==true) && (eastValid==false) && (westValid==true)) 
    {return southOrNorthOrWest();} 

    //lower right corner 
    if ((northValid==true) && (southValid==false) && (eastValid==false) && (westValid==true)) 
    {return northOrWest();} 

    //bottom border 
    if ((northValid==true) && (southValid==false) && (eastValid==true) && (westValid==true)) 
    {return eastOrNorthOrWest();} 

    //middle 
    if ((northValid==true) && (southValid==true) && (eastValid==true) && (westValid==true)) 
    {return any();} 


    System.out.println("go where a llegado a retornar null"); 
    return null; 

} 


void DFS(int i, int j){ // i,j identifies the vertex 

    boolean northValid= false; 
    boolean southValid= false; 
    boolean eastValid = false; 
    boolean westValid = false; 


    int iNorth, jNorth; 
    int iSouth, jSouth; 
    int iEast, jEast; 
    int iWest, jWest; 

    iNorth=i-1; 
    if (!(iNorth<0)) northValid=true; 

    iSouth=i+1; 
    if(!((iSouth)>=M)) southValid=true; 

    jEast=j+1; 
    if(!((jEast)>=N)) eastValid=true; 

    jWest= j-1; 
    if (!(jWest<0)) westValid=true; 



    if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited 

     adjacencyMatrix[i][j]=0; //mark the vertex as visited 
     IJ ij = new IJ(i,j); 
     orderOfVisits.add(ij); //add the vertex to the visit list 
     System.out.println("Visit i,j: " + i +" " +j); 






//boolean wentNorth = false; 
//boolean wentSouth=false; 
//boolean wentEast = false; 
//boolean wentWest = false; 

    // if (where!=null) 
     for (int rows=i; rows<M; rows++) 
      for (int cols=j; cols<N; cols++){ 

     //normal DFS 

      String where = goWhere(northValid, southValid, eastValid, westValid, i,j); 

      if (where.equals("north")) 
      { 
       DFS(iNorth,j); 
       //wentNorth=true; 
      } 



      if (where.equals("south")){ 
       DFS(iSouth,j); 
      } 

      if(where.equals("east")){ 
       DFS(i, jEast); 
      } 

      if (where.equals("west")){ 
       DFS(i,jWest); 
      } 


//   if(northValid) 
//   { 
//    DFS(iNorth,j); 
//   } 
// 
//   if(southValid){ 
//    DFS(iSouth,j); 
//   } 
// 
//   if(eastValid){ 
//    DFS(i, jEast); 
//   } 
// 
//   if(westValid){ 
//    DFS(i,jWest); 
//   } 


     } 



    } 






// boolean southValid; 
// int iSouth, jSouth; 
// iSouth=i+1; jSouth=j; 
// if (iSouth>=M){ 
//  southValid=false; 
// } 
// else { 
//  southValid=true; 
// } 
// 
// boolean southUnvisited; 
// if ((southValid)&& 
//   (adjacencyMatrix[iSouth][jSouth]==-1)){ 
//  southUnvisited=true; 
// } 
// else{ 
//  southUnvisited=false; 
// } 
// 
// 
// boolean northValid; 
// int iNorth, jNorth; 
// iNorth=i-1; jNorth=j; 
// 
// if(iNorth<0){ 
//  northValid=false; 
// } 
// 
// else{ 
//  northValid=true; 
//  } 
// 
// boolean northUnvisited; 
// if ((northValid) 
//   &&(adjacencyMatrix[iNorth][jNorth]==-1)){ 
//  northUnvisited=true; 
// } 
// else { 
//  northUnvisited=false; 
// } 
// 
// boolean westValid; 
// int iWest, jWest; 
// iWest =i; jWest=j-1; 
// if (jWest<0){ 
//  westValid=false; 
// } 
// else { 
//  westValid=true; 
// } 
// 
// boolean westUnvisited; 
// 
// 
// if ((westValid)&&(adjacencyMatrix[iWest][jWest]==-1)) 
//  { 
//  westUnvisited=true; 
//  } 
//  else { 
//  westUnvisited=false; 
//  } 
// 
// 
// 
// boolean eastValid; 
// int iEast, jEast; 
// iEast=i; jEast=j+1; 
// if (jEast<0){ 
//  eastValid=false; 
// } 
//  else{ 
//  eastValid=true; 
// } 
// 
// boolean eastUnvisited; 
// if (eastValid&& 
//  (adjacencyMatrix[iEast][jEast]==-1)){ 
//  eastUnvisited=true; 
// } 
// else { 
//  eastUnvisited=false; 
// } 
// 
// double lottery = Math.random(); 
// 
// 
// 
// boolean canVisitNorth=northUnvisited&&northValid; 
// boolean canVisitSouth=southUnvisited&&southValid; 
// boolean canVisitEast=eastUnvisited&&eastValid; 
// boolean canVisitWest=westUnvisited&&westValid; 
// 
// if (lottery>0.75D) 
// { 
// 
//  if(canVisitNorth) 
//   DFS(iNorth, jNorth); 
// 
//  else if(canVisitSouth) 
//   DFS(iSouth, jSouth); 
// 
//  else if(canVisitEast) 
//   DFS(iEast, jEast); 
// 
//  else if(canVisitWest) 
//   DFS(iWest, jWest); 
// 
//  } 
// 
//  else if(lottery < 0.25D) 
//  { 
// 
//  if(canVisitSouth) 
//   DFS(iSouth, jSouth); 
// 
//  else if(canVisitNorth) 
//   DFS(iNorth, jNorth); 
// 
//  else if(canVisitEast) 
//   DFS(iEast, jEast); 
// 
//  else if(canVisitWest) 
//   DFS(iWest, jWest); 
// 
// 
//  } 
// 
//  else if((lottery >= 0.25D)&& 
//    (lottery<0.5D)) 
//  { 
//  if(canVisitEast) 
//   DFS(iEast, jEast); 
// 
//   else if(canVisitSouth) 
//   DFS(iSouth, jSouth); 
// 
//  else if(canVisitNorth) 
//   DFS(iNorth, jNorth); 
// 
//  else if(canVisitWest) 
//   DFS(iWest, jWest); 
// 
// 
//  } 
// 
// else if((lottery >= 0.5D)&& 
//    (lottery<0.75D)) 
//  { 
// 
//  if(canVisitWest) 
//   DFS(iWest, jWest); 
// 
//  else if(canVisitEast) 
//   DFS(iEast, jEast); 
// 
//   else if(canVisitSouth) 
//   DFS(iSouth, jSouth); 
// 
//  else if(canVisitNorth) 
//   DFS(iNorth, jNorth); 
// 
// 
//  } 





} //end DFS 

// 
} 


public class Main { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     // TODO code application logic here 



    Graph theGraph = new Graph(3,3); 
    theGraph.DFS(0,0); 



    } 

}

這段代碼是給我像輸出：

Visit i,j: 0 0 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3 
Visit i,j: 1 0 
Visit i,j: 2 0

即使我驗證下一步的位置（通過布爾southValid，eastValid等）

來源

2011-04-28 andandandand

我沒有經歷過所有的代碼看，但我看到了一些令人費解的權利了。我認爲你的構造函數變量是IJ類的倒退。它看起來像你正在設置你的構造函數變量等於你的實例變量。 – Jason 2011-04-28 22:11:34

在你的方法'northOrEast'你有時候會返回''南部''。 – Jason 2011-04-28 22:50:45

我有一個建議，改變你的goWhere方法，因爲所有方向的所有方向是相同的權重，當涉及到選擇哪條路。

String goWhere (boolean northValid, boolean southValid, boolean eastValid, boolean westValid){ 

    java.util.Random r = new java.util.Random(); 
    ArrayList<String> valids = new ArrayList<String>(); 
    if(northValid) { valids.add("north"); } 
    if(southValid) { valids.add("south");} 
    if(eastValid) { valids.add("east"); } 
    if(westValid) { valids.add("west"); } 

    if (valids.size() > 1) { 
     int rand = r.nextInt(valids.size()); 
     return valids.get(rand); 
    } else { return null; } 
}

我認爲你可以擺脫其他方向查找方法。我認爲有一些bug仍然存在，其中我或j在矩陣邊界之外，但我認爲這種方法改變可能會消除一些併發症。請參閱上面有關在「northOrEast」方法中返回「南」的註釋。

此外，請考慮使用常量爲您的方向。這將有助於防止輸入錯誤，編譯器會抓住它。

public static final int NORTH = 0; 
public static final int SOUTH = 1; 
public static final int EAST = 2; 
public static final int WEST = 3;

然後，而不是做字符串比較，這樣做：

if (Graph.EAST == where) { ... }

我覺得有一個問題設置您的有效布爾值。相反的：

if (!(iNorth<0)) northValid=true;

嘗試：

northValid = (iNorth >= 0);

有沒有必要在北方的情況下的一個問題，但它是假的有點混亂測試，如果事情是不到別的東西。

當您比較M或N時，您使用>來指示它無效。我想南，例如，如果無效的，如果它> = M.或者只是做：

southValid = (iSouth < M);

來源

2011-04-28 23:02:40 Jason

添加

private boolean boundariesOK(int i, int j) { 
    return i >= 0 && j >= 0 && i < this.M && j < this.N; 
}

並更改該方法決定

if (boundariesOK(i,j) && adjacencyMatrix[i][j] == -1) { // if the vertex is unvisited

您的代碼正在嘗試訪問矩陣中的無效位置（無雙關注=））。

這是第一次黑客入侵。現在可以看到DFS部分，您的代碼應該能夠找到網格中的所有位置，而目前它沒有。

來源

2011-04-28 21:42:21 Niloct

我認爲'boundariesOK''方法對於完整性檢查（斷言或某事）是很好的，但是如果代碼依賴於它，我認爲它隱藏了一個錯誤，即允許代碼進入不可接受的狀態。 – Jason 2011-04-28 23:25:56

我提出的改變與他的問題直接相關，只需很少的改動即可修復代碼。我可以像你一樣提出許多改進建議，但我的意思是讓他擺脫這個錯誤並自己找出其他問題。 – Niloct 2011-05-01 03:44:56

Java：麻煩隨機DFS運行建立迷宮

回答

相關問題