Я работал над этим кодом некоторое время и не могу заставить его работать.Я начал несколько раз.Я не уверен, что моя логика выключена или я мог бы сделать что-то лучше.Любое предложение в правильном направлении или новые идеи, которые можно попробовать, будут полезны.Я понимаю, что лабиринт можно решить рекурсивно, но для этой части задания мне нужно использовать стек.
Я создал два стека.Один для пути, другой для пятен, которые я уже искал.В идеале я бы проверил, содержит ли искомый путь следующую точку в направлении.Если это так, он проверяет другое направление.
Пример лабиринта
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 1 0 11
0 1 0 0 0
Кажется, мой алгоритм застрял между 2,3 и 2,4.Никогда не исследует 1,4 или 0,4.Я вижу, что он продолжает подпрыгивать между 2,3 и 2,4 в бесконечном цикле.Так что, похоже, мой искомый.contains () не работает должным образом.Любое предложение, чтобы исправить мой искомый стек?В идеале, когда я запускаю свой код.Я хочу, чтобы он проверил Восток, Юг, Запад, тогда Север уже был обыскан или нет.Если все точки были проверены, он извлечет последнюю позицию из моего стека путей, используя current = path.pop внутри цикла while, и повторите.
Позиция - это пользовательский класс.Я рассмотрел добавление предыдущей переменной позиции в конструктор в классе позиции, но, похоже, в этом нет необходимости, если я смогу заставить свой стек работать.Если я ошибаюсь, пожалуйста, дайте мне знать.
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;
}