降低 Java 中 BFS 的复杂性

Question

我正在尝试为算法问题实施解决方案，其中：

”给定球体进入的矩形空间的地图，以及你的初始 位置，你的任务是计算到达目的地所需的最少移动次数 带你回家的洞（让你不安的不是翻滚，而是 撞到东西）。空间的每个位置要么是空的，要么包含一个 障碍物或洞。 球体只能在平行的方向上穿过空白位置 到地图的两侧。一旦球体开始移动，它只会在碰到一个 障碍物或它从洞里掉下来。如果球体从地图的一侧掉落，则没有 再次回到地图上的方式，你将永远无法回家。”

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;
    }

虽然我写的代码能够计算输出所需的结果，但它似乎太慢了，因为我在提供的平台上测试它时得到“超过时间限制”。

我可以做些什么来降低这段代码的复杂性？甚至可以减少循环吗？

Sample Input:
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

Sample Output:
4
1
Stuck

我尝试使用有向图，它没有帮助我，我尝试用 if 检查 4 个方向，它也有帮助。所以我不确定我能做什么。

Answer 1

也许你可以通过记住之前的走法来优化，只处理正交走法。

然后

current[3]

给出允许移动的索引，并且结构将包含每个方向

{{2,3},{0,1},{2,3},{0,1},{0,1,2,3}}

的表。这里一个虚拟的 previous direction=4 将被用作第一个 previous direction 并允许扫描所有方向。

这只会通过乘数改变复杂性，因为尝试相同的方向和相反的方向将给出一个已经看到的单元格并且不会填充队列。

注意：当您希望放弃移动时，边缘似乎被视为墙。

Answer 2

我认为，当球体撞到障碍物时，您还需要保存有关所选方向的信息，而不仅仅是障碍物坐标。

public static void main(String[] args) {
    char[][] map = new char[][]{
            /*0*/".....O..............".toCharArray(),
            /*1*/"OOO.OO.OOOOOOOO.....".toCharArray(),
            /*2*/"O.............O..OOO".toCharArray(),
            /*3*/"O.O..O.............O".toCharArray(),
            /*4*/"O.O..O........OOO..O".toCharArray(),
            /*5*/"..O..O..........O..O".toCharArray(),
            /*6*/"..O..OOOO.......O..O".toCharArray(),
            /*7*/"..O..........H.....O".toCharArray(),
            /*8*/"..O................O".toCharArray(),
            /*9*/"..OOOOOOOOOOOOOOOOOO".toCharArray(),
            /*    0123456789abcdefgijk  */
    };

    System.out.println(bfs(map, 7, 0));
    System.out.println(bfs(map, 7, 4));
    System.out.println(bfs(map, 0, 10));
    System.out.println(bfs(map, 0, 0));
    System.out.println(bfs(map, 9, 1));
    System.out.println(bfs(map, 8, 4));
    System.out.println(bfs(map, 2, 4));
}


static int bfs(char[][] map, int startRow, int startColumn) {
    int rows = map.length;
    int columns = map[0].length;

    int[][] seen = new int[rows][columns];

    int holeRow = -1;
    int holeColumn = -1;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if ('H' == map[i][j]) {
                holeRow = i;
                holeColumn = j;
                break;
            }
        }
    }


    int[] dr = {-1, 0, 1, 0};
    int[] dc = {0, 1, 0, -1};
    int[] pair = {2, 3, 0, 1};

    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < 4; i++) {
        queue.add(new int[]{startRow, startColumn, 0, i});
    }

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

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

        int newRow = row + dr[dir];
        int newCol = col + dc[dir];
        while (true) {
            if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= columns) {
                // falls off a side
                break;
            }

            if (newRow == holeRow && newCol == holeColumn) {
                // falls through the hole
                return moves + 1;
            }

            if (map[newRow][newCol] != 'O') {
                // move forward
                newRow += dr[dir];
                newCol += dc[dir];
                continue;
            }

            // obstacle:
            //      move back and turn into
            //      perpendicular direction

            newRow -= dr[dir];
            newCol -= dc[dir];

            for (int i = 0; i < 4; i++) {
                int bit = 2 << i;
                if (i == dir || i == pair[dir]) {
                    seen[newRow][newCol] |= bit;
                }
                if ((seen[newRow][newCol] & bit) != bit) {
                    queue.add(new int[]{newRow, newCol, moves + 1, i});
                    seen[newRow][newCol] |= bit;
                }
            }

            break;

        }
    }
    return -1;
}