java - 如何快速进行广度优先搜索？

因此，我平均能够在22毫秒内解决200x200的迷宫（就像pacman，没有任何图形）。我使用了四个邻居（上，右，左和下）的节点链表。我使用了FileWriter，文件读取器，缓冲方法以及BFS算法来进行从起点到目标的搜索。如前所述，所有这些任务在200x200迷宫上总共耗时22毫秒。
我想知道专门使用Queue接口是否有助于加快流程。我知道LinkedList实现了Queue，所以我只用了LinkedList。关于提高速度有什么建议吗？

注意：我尽力使每种方法都避免过多的for循环。我仅在编写文件时才使用两个for循环。

最佳答案

如果您使用网格和递归，则可以完全避免使用循环。

就像是

public static void main(String... ignored) {
    search(2, 2, "..........\n" +
            ".########.\n" +
            "...#......\n" +
            "#####.####\n" +
            "X.........\n");
}

public static boolean search(int x, int y, String grid) {
    String[] rows = grid.split("\n");
    char[][] grid2 = new char[rows.length][];
    for (int i = 0; i < rows.length; i++) {
        String row = rows[i];
        grid2[i] = row.toCharArray();
    }
    return search(x, y, grid2);
}

public static boolean search(int x, int y, char[][] grid) {
    if (x < 0 || x >= grid.length || y < 0 || y > grid[0].length)
        return false;
    char ch = grid[x][y];
    if (ch == 'X') {
        System.out.println("End " + x + ", " + y);
        return true;
    }
    // - is been here before
    // # is a wall.
    if (ch == '-' || ch == '#') {
        return false;
    }
    grid[x][y] = '-'; // been here before.
    boolean found = search(x - 1, y, grid) || search(x + 1, y, grid)
            || search(x, y - 1, grid) || search(x, y + 1, grid);
    grid[x][y] = ch;
    if (found)
        System.out.println("... " + x + ", " + y);
    return found;
}

打印（以相反的顺序以避免创建坐标列表）

End 4, 0
... 4, 1
... 4, 2
... 4, 3
... 4, 4
... 4, 5
... 3, 5
... 2, 5
... 2, 6
... 2, 7
... 2, 8
... 2, 9
... 1, 9
... 0, 9
... 0, 8
... 0, 7
... 0, 6
... 0, 5
... 0, 4
... 0, 3
... 0, 2
... 0, 1
... 0, 0
... 1, 0
... 2, 0
... 2, 1
... 2, 2