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

我建议使用 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面墙——第一行、最后一行、第一列、最后一列。假设这些墙被表示为'*'）

Answer 2

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

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

所以我将 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 到当前位置的路径数。 A 处的值 0 应该设置为 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 路径）。此解决方案具有线性时间复杂度。

Java 在墙内迷宫并找到所有可能的路径

Java maze inside of walls and get all possible paths

java

algorithm

maze

text-files

multidimensional-array