在多维矩阵上进行 BFS 时出现循环引用无限循环问题

Question

在多维矩阵上进行广度优先搜索时，某些单元格被阻塞，我得到循环引用并进入无限循环。

如何回溯 BFS 搜索以返回从节点 B 到节点 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(); //I've hardcoded an example matrix
        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<>();
    }
}

我想从nodeB转到nodeS，由于某种原因，即使它找到了正确的路径，但在回溯时却陷入了无限循环。

Answer 1

想通了-想为其他人发帖：p

public class Bot_1 extends Bot{

public Bot_1(Ship ship){
    super(ship);
}

public List<Cell> breadthFirstSearch(Ship ship, Cell hProbCell){

    Cell bot = new Cell(ship.getBot().getX(), ship.getBot().getY());
    Cell dest = new Cell(hProbCell.getX(), hProbCell.getY());
    Queue <Cell> queue = new LinkedList<>();
    boolean visited[][] = new boolean[ship.getSize()][ship.getSize()];
    Cell[][] parent = new Cell[ship.getSize()][ship.getSize()];
    Cell[][] cells = new Cell[ship.getSize()][ship.getSize()];
    for (int i = 0; i < ship.getSize(); i++) {
        for (int j = 0; j < ship.getSize(); j++) {
            if (ship.isOpenCell(i,j)) {
                cells[i][j] = new Cell(i, j, Integer.MAX_VALUE, null);
            }
            visited[i][j] = false;
        }
    }

    //Starting Node
    queue.add(cells[bot.getX()][bot.getY()]);
    visited[bot.getX()][bot.getY()] = true;
    parent[bot.getX()][bot.getY()] = null;
    Cell current = null;
    Cell previous = null;

    while(!queue.isEmpty()){

        // Assign current node & Moves to next cell in queue
        previous = current;
        current = queue.poll();

        // Check if bot = button
        if(current.equals(dest)){
            List<Cell> path = new ArrayList<>();
            Cell node = current;
            if (node.getParentCell() == null || node == null) {
                Collections.reverse(path);
                return path;
            }
            else {
                while(node.getParentCell() != null){
                    path.add(node);
                    node = node.getParentCell();
                }
                Collections.reverse(path);
                return path;
            }
        }
        //Add children of bot to queue
        else{
            for(Cell neighbor : getBotNeighbors(current)){
                if((neighbor.isOpenCell(ship)) && visited[neighbor.getX()][neighbor.getY()] == false){
                    int dist = current.getDist() + 1;
                    if (dist < neighbor.getDist()) {
                        visited[neighbor.getX()][neighbor.getY()] = true;
                        cells[neighbor.getX()][neighbor.getY()].setDist(dist);
                        cells[neighbor.getX()][neighbor.getY()].setParentCell(cells[current.getX()][current.getY()]);
                        queue.add(cells[neighbor.getX()][neighbor.getY()]);
                    }
                }
            }
        }
    }
    System.out.println("No path exists between bot and button.");
    return new ArrayList<>();
}

}