java - 使用堆栈解决迷宫

Question

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

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

迷宫示例

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 从我的路径堆栈中弹出最后一个位置并重复。

位置是一个自定义类。我考虑过向位置类中的构造函数添加一个先前的位置变量，但如果我能让我的路径堆栈工作，似乎不需要。如果我在这方面有误，请告诉我。

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

Answer 1

我猜想问题不在于您发布的代码，而在于 Position 类。如果您没有在 Position 类中覆盖 hashcode() 和 equals()，则此处的 contains() 比较将寻找对象相等性.

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

参见 this answer了解更多。