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如下（请注意，我颠倒了尺寸，因为您的第二个示例表明输入的第一行按该顺序排列它们）：&nbsp; &nbsp; int[][] mat = new int[Integer.valueOf(dimensions[1])]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[Integer.valueOf(dimensions[0])];&nbsp; &nbsp; int colA = mat[0].length;&nbsp; &nbsp; int rowA = 0;&nbsp; &nbsp; int colB = colA;&nbsp; &nbsp; int rowB = 0;&nbsp; &nbsp; for (int i = 0; i < mat.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; String currLine = lines.get(i+1);&nbsp; &nbsp; &nbsp; &nbsp; int j = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (char c : currLine.toCharArray()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mat[i][j] = c == '*' ? -1 : 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (c == 'B') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (colA > j) return 0; // B unreachable from A&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rowB = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; colB = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else if (c == 'A') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (colB < j) return 0; // B unreachable from A&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; rowA = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; colA = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }通过此设置，您可以重复mat存储从 A 到当前位置的路径数。值 0 atA应设置为 1（从 A 到 A 仅有一条路径），然后将上方和左侧单元格中的值相加，确保 -1 被视为 0。&nbsp; &nbsp; mat[rowA][colA] = 1;&nbsp; &nbsp; for (int i = rowA; i <= rowB; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for (int j = colA; j <= colB; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (mat[i][j] == 0) { // not a wall?&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // count the number of paths that come from above,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp;plus the number of paths that come from the left&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mat[i][j] = Math.max(0, mat[i-1][j]) + Math.max(0, mat[i][j-1]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; 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 {&nbsp; &nbsp; public static void main(String[] args) throws IOException, URISyntaxException {&nbsp; &nbsp; &nbsp; &nbsp; Path mazePath = Paths.get( MethodHandles.lookup().lookupClass().getClassLoader()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .getResource("maze.txt").toURI());&nbsp; &nbsp; &nbsp; &nbsp; File mazeFile = mazePath.toFile();&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(getPossiblePaths(mazeFile));&nbsp; &nbsp; }&nbsp; &nbsp; private static int getPossiblePaths(File f) throws IOException {&nbsp; &nbsp; &nbsp; &nbsp; // read input file then put it on list string&nbsp; &nbsp; &nbsp; &nbsp; List<String> lines = Files.lines(f.toPath()).collect(Collectors.toList());&nbsp; &nbsp; &nbsp; &nbsp; // get the row and column (dimensions)&nbsp; &nbsp; &nbsp; &nbsp; String[] dimensions = lines.get(0).split(",");&nbsp; &nbsp; &nbsp; &nbsp; //initalize sub matrix of the maze dimensions and ignoring the top and bottom walls&nbsp; &nbsp; &nbsp; &nbsp; int[][] mat = new int[Integer.valueOf(dimensions[0]) - 2 ][Integer.valueOf(dimensions[1]) - 2];&nbsp; &nbsp; &nbsp; &nbsp; int fromRow = -1, fromCol = -1, toRow = -1, toCol = -1;&nbsp; &nbsp; &nbsp; &nbsp; for( int i = 2 ; i < lines.size() - 1&nbsp; ; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; String currLine = lines.get(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int j = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(char c : currLine.toCharArray()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch(c) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case '*':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue; // for loop&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'A':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mat[i-2][j] = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fromRow = i-2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fromCol = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'B':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mat[i-2][j] = 2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; toRow = i-2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; toCol = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; default:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mat[i-2][j] = 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return getPossiblePathsRecursive(mat, fromRow, fromCol, toRow, toCol);&nbsp; &nbsp; }&nbsp; &nbsp; private static int getPossiblePathsRecursive(int[][] mat, int i, int j, int rows, int columns) throws IOException {&nbsp; &nbsp; &nbsp; &nbsp; if(i > rows || j > columns) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if(mat[i][j] == 2) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return getPossiblePathsRecursive(mat, i+1, j, rows, columns) +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;getPossiblePathsRecursive(mat, i, j + 1, rows, columns);&nbsp; &nbsp; }}注意： 1. 跳过验证步骤（假设输入数据采用有效格式） 2. 忽略墙壁（假设始终有 4 堵墙 - 第一行、最后一行、第一列、最后一列。这些墙假设表示为“*”）