Я создал два стека. Один для пути, другой для мест, которые я уже искал. В идеале я бы проверил, содержит ли искомый путь следующую точку в направлении. Если это так, он проверяет другое направление.
Образец лабиринта
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() не работает должным образом. Любое предложение исправить мой обысканный стек? В идеале, когда я запускаю свой код. Я хочу, чтобы он проверил Восток, Юг, Запад, а затем Север уже был обыскан или нет. Если все точки были проверены, он вытолкнет последнюю позицию из моего стека путей, используя current= path.pop внутри цикла while, и повторит.
Позиция — это настраиваемый класс. Я подумал о добавлении переменной предыдущей позиции в конструктор в классе позиции, но, похоже, это не нужно, если я могу заставить работать свой стек путей. Если я ошибаюсь в этом, пожалуйста, дайте мне знать.
class Position{
public int i; //row
public int j; //column
public char val; //1, 0, or 'X'
// reference to the previous position (parent) that leads to this position on a path
Position parent;
Position(int x, int y, char v){
i=x; j = y; val=v;
}
Position(int x, int y, char v, Position p){
i=x; j = y; val=v;
parent=p;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + i;
result = prime * result + j;
result = prime * result + ((parent == null) ? 0 : parent.hashCode());
result = prime * result + val;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Position other = (Position) obj;
if (i != other.i)
return false;
if (j != other.j)
return false;
if (parent == null) {
if (other.parent != null)
return false;
} else if (!parent.equals(other.parent))
return false;
if (val != other.val)
return false;
return true;
}
}
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;
}
