墙内的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*
*      *
********

因此，对于我当前的代码，它正在获取尺寸(第一行)并移除迷宫的顶部和底部(边界)。所以目前 ma​​t 数组中只存储了 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 直接到达，否则 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 路径到达那里时) .该解决方案具有线性时间复杂度。