获取迷宫中的所有路径（Horizontal/Vertical 仅移动）

Question

我试图在迷宫中找到所有路径，其中唯一有效的移动是向右（“H”）或向下（“V”）。我想要 return 这些路径的字符串列表。

我的代码目前没有 return 这些字符串的列表，我认为错误在于尝试使用相同的 String 对象以递归方式构建答案。如果有人可以帮我解决这个问题（或他们可能看到的任何其他错误），我将不胜感激！

我考虑过制作坐标 class，这是正确的做法吗？如果是这样，我不确定如何使用此 class 来制作正确的字符串。这就是我认为 class 的样子：

 public static class Coordinate {
        public int row, col;
        public String path;
        
        public Coordinate (int row, int col) {
            this.row = row;
            this.col = col;
            path = new String();
        }
        
        public addLetter(String s) {
            path = path + s;
        }
    }

问题的示例，如果我的矩阵大小为 3：

 0  1 2 
0 X H H
1     V
2     V

 0  1 2 
0 X H 
1   V H
2     V

 0  1 2 
0 X H 
1   V
2   V H

 0  1 2 
0 X 
1 V H H
2     V

 0  1 2 
0 X 
1 V H 
2   V H

 0  1 2 
0 X 
1 V  
2 V H H

And all the possible strings are:
- HHVV, HVHV, HVVH, VHHV, VHVH, VVHH

所以如果输入 n 等于 3，函数应该 return 一个字符串列表 ["HHVV", "HVHV", "HVVH", "VHHV", "VHVH", "VVHH "].

如果输入n为2，函数应该return： [“HV”，“VH”]。

class Result {
  
    public static List<String> getSafePaths(int n) {
    //do a dfs on the graph
        List<String> paths = new ArrayList<>();
 
        int er = n - 1;
        int ec = n - 1;
        int[][] matrix = new int[n][n]; 
        matrix[0][0] = 2; //all visited nodes changed to two
   
        getPaths(matrix, 0, 0, er, ec, paths, "");
    
        
        return paths;
    }
    
    public static void getPaths(int[][] matrix, int sr, int sc, int er, int ec, List<String> paths, String s) {
        if(sr == er && sc == ec) {
            paths.add(new String(s));
        }
        
        final int[][] SHIFTS = {
            {0, 1}, //go right
            {1,0} // go down
        };
        
        for(int[] shift : SHIFTS) {
            int right = -1;
            int down = -1;
            //are we going down or right? Need this to add correct letter
            if(shift[0] == 0) {
                right = 1;
            }
            else {
                down = 1;
            }
            
            String letter = valid(matrix, sr + shift[0], sc + shift[1], right, down);
            if(letter != null) {
                
                if(letter == "H") {

                    s = s + "H";
                   
                }
                if(letter == "V") {

                    s = s + "V";

                }
              
                matrix[sr + shift[0]][sc + shift[1]] = 2;
                
                getPaths(matrix, sr + shift[0], sc + shift[1], er, ec, paths, s);
            } 
        }
    }
    
    public static String valid(int[][] matrix, int sr, int sc, int right, int down) {
        if(sr >= 0 && sr < matrix.length && sc >= 0 && sc < matrix[sr].length && matrix[sr][sc] != 2) {
            if(right == 1) {
                return "H";
            }
            else {
                return "V";
            }
        }
        return null;
    }

}

Answer 1

主要问题（但肯定不是唯一的）是访问位置的标记（通过将matrix的值设置为2来标记）。一旦一个位置被标记为 2，后面的搜索就不能在路径中包含这个位置。以目标位置为例。到达后，它被标记为 2，这意味着后续搜索无法再到达它。这就是为什么 paths 搜索完成后只包含一个路径的原因。事实上，在这种情况下，根本不需要标记已访问的位置。唯一可能的移动是向下和向右，所以搜索不能return到同一个位置两次。
只需注释掉 matrix[currentRow + shift[0]][currentColumn + shift[1]] = 2; 即可获得更多路径（并揭示更多错误）。

边注：

            /* check for equality  between strings by letter.equals("H")
            if(letter == "H") {
                s = s + "H";
            }
            if(letter == "V") {
                s = s + "V";
            }
            */

            //the two if blocks are not needed. letter can only be V or H so simply do:
            s=s+letter;  //or s+=letter  or s=s.concat(letter)

获取迷宫中的所有路径（Horizontal/Vertical 仅移动）

Get all Paths (Horizontal/Vertical Moves Only) in a Maze

java

graph

depth-first-search

breadth-first-search

maze