java - 有效地搜索二维矩阵的多个项目

Question

我有一个 25x25 的网格，看起来像这样。在网格中放置了两个随机的字符串序列，我正在尝试开发几种有效的方法来搜索网格并找到每个位置的点。

我查看了几个搜索二维数组的算法示例，大多数算法似乎都专注于查找单个字符或数字等。

在这个特定实例中，我有哪些搜索选项？我实现了这样一个基本步骤:

public void search(String[][] grid) {
    int cellsSearched = 0;
    List<Point> cLocations = new ArrayList<>();
    List<Point> sLocations = new ArrayList<>();

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (cLocations.size() == 5 && sLocations.size() == 3) break;
            if (grid[i][j].equals("S")) {
                sLocations.add(new Point(i, j));
            } else if (grid[i][j].equals("C")) {
                cLocations.add(new Point(i, j));
            }
            cellsSearched++;
        }
    }
}

但这显然不是最有效的搜索方式。

我也想过把grid分成一个象限，一次搜索一个象限，但是这样好像还是有太多的隐患。 (例如，两个序列都位于搜索的最后一个象限中)。

我的问题是，如何以尽可能少的步骤搜索此网格并收集其序列中每个字符的坐标？

Answer 1

您可以使用一种技巧来改进搜索的运行时间。
但是因为它是一个网格，而且因为我们没有任何关于 'S' 和 'C' 位置的信息，所以时间复杂度将保持不变O(n^2)。
有了这个，

一旦您点击 'S' 或 'C'，您实际上可以从那里存储它们的整个序列。您基本上必须检查当前字符的两边是否有相同的字符并继续。
你可以有一个额外的 2D 数组 boolean 来跟踪哪些点包含在 ArrayList 中。
这是获得更好想法的代码:

public void search(String[][] grid) {
    int cellsSearched = 0;
    List<Point> cLocations = new ArrayList<>();
    List<Point> sLocations = new ArrayList<>();

    boolean[][] map = new boolean[grid.length][grid[0].length];

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (cLocations.size() == 5 && sLocations.size() == 3) break;
            if(!map[i][j]) {
                if (grid[i][j].equals("S")) {
                    getSeries(i, j, "S", grid, map, sLocations);
                } else if (grid[i][j].equals("C")) {
                    getSeries(i, j, "C", grid, map, sLocations);
                }
            }
            cellsSearched++;
        }
    }
}

public boolean inbounds(int i, int j, String[][] grid) {
    return ( 0 <= i && i < grid.length ) && ( 0 <= j && j < grid[i].length );
}

public void getSeries(int i, int j, String toFind,String[][] grid, boolean map[][], ArrayList<Point> locations) {

    /**
     * This function basically checks if 'i' and 'j' are safe so that accessing grid[i][j]
     * would not cause ArrayOutOfBoundsException
     */
    if(!inbounds(i, j, grid)) {
        return;
    }

    String matched = grid[i][j];
    if(!map[i][j] && matched.equals(toFind)) {
        map[i][j] = true;
        locations.add(new Point(i, j));

        // Going up
        getSeries(i - 1, j, toFind, grid, map, locations);

        // Going down
        getSeries(i + 1, j, toFind, grid, map, locations);

        // Going left
        getSeries(i, j - 1, toFind, grid, map, locations);

        // Going right
        getSeries(i, j + 1, toFind, grid, map, locations);

        /*
        (i+1, j-1) -> Going Bottom Left
        (i+1, j+1) -> Going Bottom Right

        (i-1, j-1) -> Going Top Left
        (i-1, j+1) -> Going Top Right 
        */
    }
}

您会看到，一旦您点击了 'S' 或 'C'，getSeries 函数就会自动将整个序列保存到 数组列表。

正如我之前提到的，时间复杂度仍然是 O(n^2) 但它肯定会减少查找序列的步骤数。