优化Java中BFS算法复杂度：解决球体寻洞超时问题

给定球体活动的矩形空间地图与初始位置，计算到达回家洞口所需的最少移动次数。地图位置分为空区域、障碍物、洞口三类；球体仅能沿平行于地图边的方向移动，一旦启动移动，仅在碰到障碍物或落入洞口时停止，若掉落地图边界则无法返回。

已编写的Java BFS代码可得到正确结果，但测试平台出现「Time Limit Exceeded（超时）」问题。尝试过有向图、条件判断检查4个方向，均无改善。需降低代码复杂度、减少循环次数。

原代码 #

static int bfs(char[][] map, int startRow, int startColumn, int holeRow, int holeColumn) {
        int rows = map.length;
        int columns = map[0].length;
        int[] dr = { -1, 0, 1, 0 };
        int[] dc = { 0, 1, 0, -1 };
    
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][columns];
        queue.add(new int[] { startRow, startColumn, 0 });
        visited[startRow][startColumn] = true;
    
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int moves = current[2];
    
            if (row == holeRow && col == holeColumn)
                return moves;
    
            for (int i = 0; i < 4; i++) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];
    
                while (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < columns && map[newRow][newCol] != 'O') {
                    if (newRow == holeRow && newCol == holeColumn)
                        return moves + 1;
                    newRow += dr[i];
                    newCol += dc[i];
                }
    
                newRow -= dr[i];
                newCol -= dc[i];
    
                if (!visited[newRow][newCol]) {
                    queue.add(new int[] { newRow, newCol, moves + 1 });
                    visited[newRow][newCol] = true;
                }
            }
        }
        return -1;
    }

示例输入 #

10 20 3
.....O..............
OOO.OO.OOOOOOOO.....
O.............O..OOO
O.O..O.............O
O.O..O........OOO..O
..O..O..........O..O
..O..OOOO.......O..O
..O..........H.....O
..O................O
..OOOOOOOOOOOOOOOOOO
8 1
8 5
1 10

示例输出 #

4
1
Stuck

• 预处理移动终点，消除重复遍历
  原代码中每次处理一个方向时，都要从当前位置一步步移动到障碍物/洞口/边界，大地图场景下内层while循环会重复遍历大量格子。可以提前预处理每个格子在四个方向上的最终停留位置，用四个二维数组存储每个点向上、右、下、左移动后的终点坐标。预处理仅需O(rows*columns)时间，后续BFS直接取预处理结果，避免每次循环移动。

• 优化边界判断逻辑
  原代码中移动到边界外后会回退到边界内，但该位置属于无效区域，应直接跳过加入队列的步骤。移动结束后先判断终点是否在地图范围内，不在则直接跳过，无需再检查visited状态。

• 替换队列实现提升性能
  Java中LinkedList作为队列基于双向链表实现，可替换为ArrayDeque——它基于数组实现，减少了链表节点的创建和内存开销，poll()和offer()操作的性能更优。

• 提前拦截洞口判断
  预处理阶段可直接标记洞口位置，在BFS处理方向时，若预处理的终点是洞口，直接返回当前步数+1，无需再进入队列流程。

优化后代码示例 #

static int optimizedBfs(char[][] map, int startRow, int startColumn, int holeRow, int holeColumn) {
    int rows = map.length;
    int columns = map[0].length;
    // 预处理四个方向的终点：0=上，1=右，2=下，3=左
    int[][][] next = new int[4][rows][columns];

    // 预处理向上方向的终点
    for (int col = 0; col < columns; col++) {
        int lastObstacle = -1;
        for (int row = 0; row < rows; row++) {
            if (map[row][col] == 'O') {
                lastObstacle = row;
                next[0][row][col] = row;
            } else if (row == holeRow && col == holeColumn) {
                next[0][row][col] = row;
            } else {
                next[0][row][col] = lastObstacle + 1;
            }
        }
        // 反向修正，确保无障碍物时直接到达顶部
        for (int row = rows - 1; row >= 0; row--) {
            if (map[row][col] != 'O' && !(row == holeRow && col == holeColumn)) {
                if (next[0][row][col] == row && row > 0 && map[row-1][col] != 'O') {
                    next[0][row][col] = next[0][row-1][col];
                }
            }
        }
    }

    // 预处理向右方向的终点
    for (int row = 0; row < rows; row++) {
        int lastObstacle = columns;
        for (int col = columns - 1; col >= 0; col--) {
            if (map[row][col] == 'O') {
                lastObstacle = col;
                next[1][row][col] = col;
            } else if (row == holeRow && col == holeColumn) {
                next[1][row][col] = col;
            } else {
                next[1][row][col] = lastObstacle - 1;
            }
        }
        // 正向修正，确保无障碍物时直接到达右侧
        for (int col = 0; col < columns; col++) {
            if (map[row][col] != 'O' && !(row == holeRow && col == holeColumn)) {
                if (next[1][row][col] == col && col < columns - 1 && map[row][col+1] != 'O') {
                    next[1][row][col] = next[1][row][col+1];
                }
            }
        }
    }

    // 预处理向下方向的终点
    for (int col = 0; col < columns; col++) {
        int lastObstacle = rows;
        for (int row = rows - 1; row >= 0; row--) {
            if (map[row][col] == 'O') {
                lastObstacle = row;
                next[2][row][col] = row;
            } else if (row == holeRow && col == holeColumn) {
                next[2][row][col] = row;
            } else {
                next[2][row][col] = lastObstacle - 1;
            }
        }
        // 正向修正，确保无障碍物时直接到达底部
        for (int row = 0; row < rows; row++) {
            if (map[row][col] != 'O' && !(row == holeRow && col == holeColumn)) {
                if (next[2][row][col] == row && row < rows - 1 && map[row+1][col] != 'O') {
                    next[2][row][col] = next[2][row+1][col];
                }
            }
        }
    }

    // 预处理向左方向的终点
    for (int row = 0; row < rows; row++) {
        int lastObstacle = -1;
        for (int col = 0; col < columns; col++) {
            if (map[row][col] == 'O') {
                lastObstacle = col;
                next[3][row][col] = col;
            } else if (row == holeRow && col == holeColumn) {
                next[3][row][col] = col;
            } else {
                next[3][row][col] = lastObstacle + 1;
            }
        }
        // 反向修正，确保无障碍物时直接到达左侧
        for (int col = columns - 1; col >= 0; col--) {
            if (map[row][col] != 'O' && !(row == holeRow && col == holeColumn)) {
                if (next[3][row][col] == col && col > 0 && map[row][col-1] != 'O') {
                    next[3][row][col] = next[3][row][col-1];
                }
            }
        }
    }

    Queue<int[]> queue = new ArrayDeque<>();
    boolean[][] visited = new boolean[rows][columns];
    queue.add(new int[]{startRow, startColumn, 0});
    visited[startRow][startColumn] = true;

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int row = current[0];
        int col = current[1];
        int moves = current[2];

        if (row == holeRow && col == holeColumn) {
            return moves;
        }

        for (int i = 0; i < 4; i++) {
            int endRow = row;
            int endCol = col;
            switch (i) {
                case 0: endRow = next[0][row][col]; break;
                case 1: endCol = next[1][row][col]; break;
                case 2: endRow = next[2][row][col]; break;
                case 3: endCol = next[3][row][col]; break;
            }

            // 到达洞口直接返回
            if (endRow == holeRow && endCol == holeColumn) {
                return moves + 1;
            }

            // 有效位置且未访问过则加入队列
            if (endRow >= 0 && endRow < rows && endCol >= 0 && endCol < columns && !visited[endRow][endCol]) {
                visited[endRow][endCol] = true;
                queue.add(new int[]{endRow, endCol, moves + 1});
            }
        }
    }

    return -1;
}

内容的提问来源于stack exchange，提问作者Miguel Costa