BFS

适合于计算树的深度, 走迷宫等问题.

模板

public void bfs() {
    // 1. push initial state to the queue
    queue.push(initialState);

    // 2. iterate till the queue is empty
    while (!queue.isEmpty()) {
        // 2.1 poll state from the queue
        Object state = queue.poll();

        // 2.2. extend the state
        // may add new state to the queue...
    }

}

扩展

1. 使用 visited[] 来记录已经访问过的状态.
2. 使用 path[] 来记录路径(长度).

例题

走迷宫-acwing

走迷宫-acwing

public class acwing_844 {

    Queue<Position> queue;

    boolean[][] visited;
    int[][] distance;

    int[][] directions = new int[][]{
            {1, 0},
            {0, 1},
            {-1, 0},
            {0, -1}
    };

    public void walkTheMaze(int n, int m, int[][] maze) {
        queue = new LinkedList<>();

        visited = new boolean[n][m];
        distance = new int[n][m];

        // 放入初始状态
        queue.add(new Position(0, 0));
        visited[0][0] = true;
        distance[0][0] = 0;

        while (!queue.isEmpty()) {
            // 取出队头
            Position p = queue.poll();

            // 遍历四个方向
            for (int[] direction : directions) {
                int x = p.x + direction[0];
                int y = p.y + direction[1];

                // 如果能够移动, 并且没有走过该点
                if (x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0 && !visited[x][y]) {
                    // 更新状态
                    queue.add(new Position(x, y));

                    // 计算该点的距离
                    distance[x][y] = distance[p.x][p.y] + 1;

                    // 设置为以访问
                    visited[x][y] = true;
                }
            }
        }

        System.out.println(distance[n - 1][m - 1]);
    }

    public static void main(String[] args) {
        acwing_844 acwing844 = new acwing_844();
        acwing844.walkTheMaze(5, 5, new int[][]{
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 1, 0}
        });
    }

    private record Position(int x, int y) {}

}