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运行建立迷宫

回答

相关问题