1
我正在通过堆栈实现通过矩阵的DFS迭代搜索以便稍后生成迷宫。事情是卡住推的第一个元素而没有弹出它：Java：堆栈弹出（）不起作用
void DFS_I(int i, int j){ // receives starting position
IJ aux = new IJ (i,j);
int [][] movement = {{0,1},{1,0},{0,-1},{-1,0}};
Stack <IJ> stack = new Stack();
stack.push(aux);
double random;
while(!stack.empty()){
IJ temp = (IJ)stack.peek();
stack.pop();
//random=(Math.random()*4);
//System.out.println("stack size "+ stack.size());
/* int index = 0;
if ((random>=0)&&(random<1)) index = 1;
else if((random >= 1) && (random < 2)) index = 2;
else if (random>3) index = 3;
int x = temp.i + movement[index][0];
int y = temp.j + movement[index][1];
while(x<0 || x>=M || y<0 || y>=N){
random=(Math.random()*4);
index = 0;
if ((random>=0)&&(random<1)) index = 1;
else if((random >= 1) && (random < 2)) index = 2;
else if (random>3) index = 3;
x = temp.i + movement[index][0];
y = temp.j + movement[index][1];
}*/
for(int k = 0; k<4; k++){
System.out.println("k =" +k);
int x = temp.i + movement[k][0];
System.out.println("x =" +x);
int y = temp.j + movement[k][1];
System.out.println("y =" +y);
if(x<0 || x>=M || y<0 || y>=N)continue;
if(adjacencyMatrix[x][y]==0)continue;
orderOfVisits.add(new IJ(x,y));
stack.push(new IJ(x,y));
adjacencyMatrix[temp.i][temp.j] = 0;
System.out.println("visited "+ x + " "+ y);
}
}
}
全码：
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package nuevolaberinto;
import java.util.ArrayList;
import java.util.Stack;
/**
*
* @author talleres
*/
class IJ {
int i;
int j;
IJ (int i,int j){
i = this.i;
j= this.j;
visited=false;
}
boolean visited;
}
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>();
}
void DFS_I(int i, int j){ // receives starting position
IJ aux = new IJ (i,j);
int [][] movement = {{0,1},{1,0},{0,-1},{-1,0}};
Stack <IJ> stack = new Stack();
stack.push(aux);
double random;
while(!stack.empty()){
IJ temp = (IJ)stack.peek();
stack.pop();
//random=(Math.random()*4);
//System.out.println("stack size "+ stack.size());
/* int index = 0;
if ((random>=0)&&(random<1)) index = 1;
else if((random >= 1) && (random < 2)) index = 2;
else if (random>3) index = 3;
int x = temp.i + movement[index][0];
int y = temp.j + movement[index][1];
while(x<0 || x>=M || y<0 || y>=N){
random=(Math.random()*4);
index = 0;
if ((random>=0)&&(random<1)) index = 1;
else if((random >= 1) && (random < 2)) index = 2;
else if (random>3) index = 3;
x = temp.i + movement[index][0];
y = temp.j + movement[index][1];
}*/
for(int k = 0; k<4; k++){
System.out.println("k =" +k);
int x = temp.i + movement[k][0];
System.out.println("x =" +x);
int y = temp.j + movement[k][1];
System.out.println("y =" +y);
if(x<0 || x>=M || y<0 || y>=N)continue;
if(adjacencyMatrix[x][y]==0)continue;
orderOfVisits.add(new IJ(x,y));
stack.push(new IJ(x,y));
adjacencyMatrix[temp.i][temp.j] = 0;
System.out.println("visited "+ x + " "+ y);
}
}
}
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);
Double lottery = Math.random();
for (int rows=i; rows<M; rows++)
for (int cols=j; cols<N; cols++){
if (lottery>0.75D){
if(northValid)
{
DFS(iNorth,j);
}
if(southValid){
DFS(iSouth,j);
}
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
}
else if (lottery<0.25D)
{
if(westValid){
DFS(i,jWest);
}
if(eastValid){
DFS(i, jEast);
}
if(southValid){
DFS(iSouth,j);
}
if(northValid)
{
DFS(iNorth,j);
}
}
else if ((lottery>=0.25D)&&(lottery<0.5D))
{
if(southValid){
DFS(iSouth,j);
}
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
if(northValid){
DFS(iNorth,j);
}
}
else if ((lottery>=0.5D)&&(lottery<=0.75D))
{
if(eastValid){
DFS(i, jEast);
}
if(westValid){
DFS(i,jWest);
}
if(southValid){
DFS(iSouth,j);
}
if(northValid){
DFS(iNorth,j);
}
}
}
} //end nested for
} //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_I(0, 0);
// theGraph.DFS(0,0);
}
}
在这行做它“卡住了”？另外，你可以把这个'IJ temp =（IJ）stack.peek（）; stack.pop（）;'改成这个'IJ temp = stack.pop（）;'。 – Finbarr 2011-04-29 00:11:48
我仍然认为你应该改变你想要走哪条路的过于复杂的方式。看到我的建议[你的其他帖子]（http://stackoverflow.com/questions/5825185/java-trouble-randomizing-a-dfs-run-to-build-a-maze）。 – Jason 2011-04-29 00:28:27
仍然在用你的IJ构造函数做一个奇怪的事情。 – Jason 2011-04-29 00:30:14