Java迷宫墙内并获得所有可能的路径

Question

我知道这里还有很多其他迷宫求解器。虽然我想有自己的方法，但我认为我的问题与其他人有点不同。到目前为止，这就是我已经开始的事情，希望我能实现我现在的想法。    private static int getPossiblePaths(File f) throws IOException {    int counts = 0; // hope to return all possible paths    // read input file then put it on list string    List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());    // get the row and column (dimensions)    String[] dimensions = lines.get(0).split(",");    //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls    int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];        //for each line in the maze excluding the boundaries (top and bottom)    for( int i = 2 ; i < lines.size() - 1  ; i++) {        String currLine = lines.get(i);        int j = 0;         for(char c : currLine.toCharArray()) {            mat[i-2][j] = (c=='*' ? 'w' : c=='A' ? 'a' : c=='B' ? 'b' : 's');            // some conditional statements here        }      }// or maybe some conditional statements here outside of the loop    return counts;}文本文件中的迷宫看起来像这样。请注意，A 可以在任何地方并且与 B 相同。唯一允许的移动是向右和向下。5,5******A  **   **  B******上述迷宫的预期输出是 6（从 A 到 B 的可能路径）。编辑：文本文件中的迷宫也可能是这样的：8,5********* A    **     B**      *********因此，使用我当前的代码，它获取尺寸（第一行）并删除迷宫的顶部和底部部分（边界）。所以目前mat数组中只存储了 3 行字符。以及文本文件中每个字符的一些编码（#=w(wall), A=a(start), B=b(end), else s(space)）我想在 foreach 内部有一些条件语句，以便可能将每个字符存储在 ArrayList 中。尽管我不确定这种方法是否会让我的生活变得更加困难。如果你们有任何建议、技巧、建议或其他更简单的方法，我们将不胜感激！谢谢

Answer 1

创造的想法mat很好。我不会费心去去掉第一行和最后一行，因为事实上，当你保留它们时，使用它们会更容易。这样，i-1当您位于非墙壁位置时，行引用就不会超出范围。

我也不会像w在那里存储字符，而是存储特定的数字，例如 -1 表示墙壁，0 表示免费。还为“A”和“B”存储 0。当遇到这两个字母时，您可以将它们的坐标存储在特定变量中（例如rowA, colA, rowB, colB）。您可能需要检查 B 是否位于 A 的右下方，否则肯定无法从 A 到达 B。

所以我将定义mat如下（请注意，我颠倒了尺寸，因为您的第二个示例表明输入的第一行按该顺序排列它们）：

    int[][] mat = new int[Integer.valueOf(dimensions[1])]

                         [Integer.valueOf(dimensions[0])];

    int colA = mat[0].length;

    int rowA = 0;

    int colB = colA;

    int rowB = 0;

    for (int i = 0; i < mat.length; i++) {

        String currLine = lines.get(i+1);

        int j = 0;

        for (char c : currLine.toCharArray()) {

            mat[i][j] = c == '*' ? -1 : 0;

            if (c == 'B') {

                if (colA > j) return 0; // B unreachable from A

                rowB = i;

                colB = j;

            } else if (c == 'A') {

                if (colB < j) return 0; // B unreachable from A

                rowA = i;

                colA = j;

            }

            j++;

        }

    }

通过此设置，您可以重复mat存储从 A 到当前位置的路径数。值 0 atA应设置为 1（从 A 到 A 仅有一条路径），然后将上方和左侧单元格中的值相加，确保 -1 被视为 0。

    mat[rowA][colA] = 1;

    for (int i = rowA; i <= rowB; i++) {

        for (int j = colA; j <= colB; j++) {

            if (mat[i][j] == 0) { // not a wall?

                // count the number of paths that come from above,

                //   plus the number of paths that come from the left

                mat[i][j] = Math.max(0, mat[i-1][j]) + Math.max(0, mat[i][j-1]);

            }

        }

    }

    return mat[rowB][colB]; // now this has the number of paths we are looking for

虽然递归方法也可以工作，但我建议使用上述动态编程方法，因为这样可以避免多次重新计算某个单元的计数（当通过不同的 DFS 路径到达那里时）。该解决方案具有线性时间复杂度。

Answer 2

我建议使用 2 次调用进行简单的递归：向下和向右。

这是代码：

import java.io.File;

import java.io.IOException;

import java.lang.invoke.MethodHandles;

import java.net.URISyntaxException;

import java.nio.file.Files;

import java.nio.file.Path;

import java.nio.file.Paths;

import java.util.List;

import java.util.stream.Collectors;

public class JavaMazeInsideOfWallsAndGetAllPossiblePaths {

    public static void main(String[] args) throws IOException, URISyntaxException {

        Path mazePath = Paths.get( MethodHandles.lookup().lookupClass().getClassLoader()

                  .getResource("maze.txt").toURI());

        File mazeFile = mazePath.toFile();

        System.out.println(getPossiblePaths(mazeFile));

    }

    private static int getPossiblePaths(File f) throws IOException {

        // read input file then put it on list string

        List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());

        // get the row and column (dimensions)

        String[] dimensions = lines.get(0).split(",");

        //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls

        int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];

        int fromRow = -1, fromCol = -1, toRow = -1, toCol = -1;

        for( int i = 2 ; i < lines.size() - 1  ; i++) {

            String currLine = lines.get(i);

            int j = 0;

            for(char c : currLine.toCharArray()) {

                switch(c) {

                case '*':

                    continue; // for loop

                case 'A':

                    mat[i-2][j] = 0;

                    fromRow = i-2;

                    fromCol = j;

                    break;

                case 'B':

                    mat[i-2][j] = 2;

                    toRow = i-2;

                    toCol = j;

                    break;

                default:

                    mat[i-2][j] = 1;

                }

                j++;

            }

        }

        return getPossiblePathsRecursive(mat, fromRow, fromCol, toRow, toCol);

    }

    private static int getPossiblePathsRecursive(int[][] mat, int i, int j, int rows, int columns) throws IOException {

        if(i > rows || j > columns) {

            return 0;

        }

        if(mat[i][j] == 2) {

            return 1;

        }

        return getPossiblePathsRecursive(mat, i+1, j, rows, columns) +

               getPossiblePathsRecursive(mat, i, j + 1, rows, columns);

    }

}

注意： 1. 跳过验证步骤（假设输入数据采用有效格式） 2. 忽略墙壁（假设始终有 4 堵墙 - 第一行、最后一行、第一列、最后一列。这些墙假设表示为“*”）