When doing a Breadth First Search on a Multidimensional Matrix where some cells are blocked, I am getting a circular reference and going into an infinite loop.
How would I backtrack my BFS search to return a path from Node B to node S?
public class Main {
public static void main(String[] args) {
char[][] grid = {
{'x', 'x', 'x', 'x', 'o'},
{'x', 'o', 'o', 'o', 'B'},
{'s', 'o', 'x', 'o', 'o'},
{'x', 'x', 'o', 'o', 'o'},
{'x', 'o', 'x', 'x', 'o'}
};
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[i].length; j++) {
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
}
}
public class BFS{
public List<Cell> breadthFirstSearch(Cell bot, Cell button, Fire fire){
int row = ship.getSize();
int col = ship.getSize();
Queue <Cell> queue = new LinkedList<>();
Queue <Cell> visited = new LinkedList<>();
Cell[][] parent = new Cell[ship.getSize()][ship.getSize()];
//Map <Cell, Cell> parent = new HashMap<>(); // Stores child, parent
boolean matchFound = false;
//Starting Node
queue.add(bot);
visited.add(bot);
parent[bot.getX()][bot.getY()] = null;
Cell previous = null;
Cell current = null;
while(!queue.isEmpty()){
// Assign current node & Moves to next cell in queue
previous = current;
current = queue.poll();
System.out.println("LOOP Current : " + current.toString());
// Check if bot = button
if(current.equals(button)){
parent[current.getX()][current.getY()] = previous;
List<Cell> path = new ArrayList<>();
Cell node = new Cell(current.getX(), current.getY());
Cell prevNode = null;
//path.add(node);
while(node != null){
path.add(node);
node = parent[node.getX()][node.getY()];
System.out.print("CurrentNODE: " + node);
}
Collections.reverse(path);
return path;
}
//Add children of bot to queue
else{
for(Cell neighbor : getBotNeighbors(current)){
//System.out.println(neighbor);
if((!(ship.isBurning(neighbor.getX(),neighbor.getY()))) &&
(neighbor.isOpenCell(ship))){
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
parent[current.getX()][current.getY()]= neighbor;
//System.out.println("parent (key): " + current.toString() + "; (value): " + parent.get(current));
}
}
}
System.out.println();
}
return new ArrayList<>();
}
}
I want to go from B to S and for some reason even though it is finding the correct path, it is stuck in an infinite loop when backtracking.
New contributor
sjay is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.