2

我已经在这段代码上工作了一段时间,但似乎无法让它工作。我已经重新开始了很多次。我不确定我的逻辑是否错误,或者我是否可以做得更好。任何正确方向的建议或尝试的新想法都会有所帮助。我知道可以递归解决迷宫,但是对于这部分作业,我需要使用堆栈。

我创建了两个堆栈。一个用于路径,另一个用于我已经搜索过的地点。理想情况下,我会检查搜索到的路径是否包含某个方向的下一个点。如果是这样,它会检查另一个方向。

样品迷宫

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;
}
4

2 回答 2

3

解决迷宫的一个常见解决方案是BFS,它既是最优的又是完整的[如果有一个解决方案,它总是会找到一个解决方案,并且它也会找到最短的一个解决方案]。

使用堆栈实际上是模拟DFS,这不是最佳的。

关于具体问题, wherecontains()不做它的工作,如果没有类的来源,很难知道问题是什么Position,但一个可能的原因是你没有覆盖equals(),所以默认equals()仍然是检查身份,并且不是平等——这显然不是真的。

于 2012-03-12T21:31:46.033 回答
3

我猜问题出在你发布的代码上,而不是在Position课堂上。如果你没有重写hashcode()并且equals()在 Position 类中,contains()这里的比较将寻找对象相等性。

因此,当您询问是否searched.contains(east)刚刚创建east为新对象时,它将返回 false,即使east的坐标与您搜索中的坐标完全匹配。

有关更多信息,请参阅此答案

于 2012-03-12T21:50:39.237 回答