我已经在这段代码上工作了一段时间,但似乎无法让它工作。我已经重新开始了很多次。我不确定我的逻辑是否错误,或者我是否可以做得更好。任何正确方向的建议或尝试的新想法都会有所帮助。我知道可以递归解决迷宫,但是对于这部分作业,我需要使用堆栈。
我创建了两个堆栈。一个用于路径,另一个用于我已经搜索过的地点。理想情况下,我会检查搜索到的路径是否包含某个方向的下一个点。如果是这样,它会检查另一个方向。
样品迷宫
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 1 0 1 1
0 1 0 0 0
我的算法似乎卡在 2,3 和 2,4 之间。从不探索 1,4 或 0,4。我看到它在无限循环中不断在 2,3 和 2,4 之间弹跳。所以看来我的 searched.contains() 无法正常运行。有什么建议可以修复我搜索的堆栈吗?理想情况下,当我运行我的代码时。我希望它检查东、南、西然后北是否已经被搜索过。如果已检查所有点,它将在 while 循环中使用 current= path.pop 从我的路径堆栈中弹出最后一个位置并重复。
Position 是一个自定义类。我已经考虑将先前的位置变量添加到位置类中的构造函数,但如果我可以让我的路径堆栈工作,似乎不需要。如果我对此有误,请告诉我。
public static Position [] stackSearch(char [] [] maze){
//todo: your path finding algorithm here using the stack to manage search list
//your algorithm should modify maze to mark positions on the path, and also
//return array of Position objects coressponding to path, or null if no path found
ArrayDeque <Position> path = new ArrayDeque<Position>();
ArrayDeque <Position> searched = new ArrayDeque<Position>();
//creates position object
Position start = new Position(0,0,'0');
Position current;
Position north,south, east, west;
int i = 0; int j = 0;
//push (0,0) onto stack
path.push(start);
searched.push(start);
while(!path.isEmpty()){
current=path.pop();
i=current.i;
j=current.j;
if(i==maze.length-1 && j==maze.length-1 && maze[i][j]=='0'){
Position[] trail= new Position [path.size()];
while(!path.isEmpty()){
for(int k=0; k<path.size();k++){
trail[k]=path.pop();
}
return trail;
}
}
System.out.println(i +"," +j);
//check east.
east= new Position(i,j+1,'0');
south= new Position(i+1,j,'0');
west= new Position(i,j-1,'0');
north= new Position(i-1,j,'0');
if (j+1 >= 0 && j+1 < maze.length && maze[i][j+1] == '0' && searched.contains(east)==false)
{
searched.push(east);
path.push(current);
path.push(east);
}
//check south, add its position to the list.
else if (i+1 >= 0 && i+1 < maze.length && maze[i+1][j] == '0' && searched.contains(south)==false)
{
searched.push(south);
path.push(current);
path.push(south);
}
//check west.
else if (j-1 >= 0 && j-1 < maze.length && maze[i][j-1] == '0' && searched.contains(west)==false)
{
searched.push(west);
path.push(current);
path.push(west);
}
//check north
else if (i-1 >= 0 && i-1 < maze.length && maze[i-1][j] == '0' && searched.contains(north)==false)
{
searched.push(north);
path.push(current);
path.push(north);
}
}
return null;
}