在0,1矩阵中进行递归路径查找(并保存所有可能的路径)java

bweufnob 于 2021-07-09 发布在 Java

关注(0)|答案(1)|浏览(224)

我正在尝试编写一个递归方法，该方法将在不回溯到int矩阵中包含值0,1的位置的情况下查找路径。0可以踩，1不行。我还限制了一条超过50步的路径。
位置是具有行和列值（x，y）的对象。locationequals是一个函数，如果两个位置相同，则返回true；如果两个位置不相同，则返回false。map变量是我试图在其中查找路径的矩阵。

private static List<List<Location>> options = new ArrayList<List<Location>>();
public static void PathFind(List<Location> path)
{
 Location current = path.get(path.size() - 1);
    boolean done = false;
    if(locationEquals(current,new Location(24,38)))
    {
        options.add(path);
        return;
    }
    if(path.size() > 50) done = true;
    if(!done)
    {
    try
    {
    if(map[current.row][current.col + 1] == 0)
    {
    if(!path.contains(new Location(current.row, current.col + 1)))
        {
            List<Location> temp = path;
            temp.add(new Location(current.row, current.col + 1));
            PathFind(temp);
        }
    }
    }
    catch (Exception e){}
            try
    {
    if(map[current.row - 1][current.col] == 0)
    {
        if(!path.contains(new Location(current.row - 1, current.col)))
        {
            List<Location> temp = path;
            temp.add(new Location(current.row - 1, current.col));
            PathFind(temp);
        }
    }
    }
    catch (Exception e){}
    try
    {
    if(map[current.row][current.col - 1] == 0)
    {
        if(!path.contains(new Location(current.row, current.col - 1)))
        {
            List<Location> temp = path;
            temp.add(new Location(current.row, current.col - 1));
            PathFind(temp);
        }
    }
    }
    catch (Exception e){}
    try
    {
    if(map[current.row + 1][current.col] == 0)
    {
        if(!path.contains(new Location(current.row + 1, current.col)))
        {
            List<Location> temp = path;
            temp.add(new Location(current.row + 1, current.col));
            PathFind(temp);
        }
    }
    }
    catch (Exception e){}
    }

执行以下代码后，“options”为空，这意味着它找不到方法。但是在这个矩阵中肯定有一个方法，所以在我的代码中我找不到一个bug。

Java Matrix recursion

来源：https://stackoverflow.com/questions/41451079/recursive-path-finding-in-0-1-matrix-and-saving-all-possible-paths-java

1条答案

按热度按时间

zwghvu4y1#

问题是，并不是每次进入递归的下一步时都要创建一个新列表（temp变量并不是真正的临时变量，因为它只是对路径的引用，而不是它的副本）。
为了解决这个问题，我把 List<Location> temp = path; 与 List<Location> temp = new ArrayList<>(path); 所以代码是：

private static List<List<Location>> options = new ArrayList<List<Location>>();
public static void PathFind(List<Location> path) {
    Location current = path.get(path.size() - 1);
    boolean done = false;
    if (locationEquals(current, new Location(24, 38))) {
        options.add(path);
        return;
    }
    if (path.size() > 50) done = true;
    if (!done) {
        try {
            if (map[current.row][current.col + 1] == 0) {
                if (!path.contains(new Location(current.row, current.col + 1))) {
                    List<Location> temp = new ArrayList<>(path);
                    temp.add(new Location(current.row, current.col + 1));
                    PathFind(temp);
                }
            }
        } catch (Exception e) {
        }
        try {
            if (map[current.row - 1][current.col] == 0) {
                if (!path.contains(new Location(current.row - 1, current.col))) {
                    List<Location> temp = new ArrayList<>(path);
                    temp.add(new Location(current.row - 1, current.col));
                    PathFind(temp);
                }
            }
        } catch (Exception e) {
        }
        try {
            if (map[current.row][current.col - 1] == 0) {
                if (!path.contains(new Location(current.row, current.col - 1))) {
                    List<Location> temp = new ArrayList<>(path);
                    temp.add(new Location(current.row, current.col - 1));
                    PathFind(temp);
                }
            }
        } catch (Exception e) {
        }
        try {
            if (map[current.row + 1][current.col] == 0) {
                if (!path.contains(new Location(current.row + 1, current.col))) {
                    List<Location> temp = new ArrayList<>(path);
                    temp.add(new Location(current.row + 1, current.col));
                    PathFind(temp);
                }
            }
        } catch (Exception e) {
        }
    }
}

赞(0）回复(0）举报 2021-07-09

我来回答

在0,1矩阵中进行递归路径查找(并保存所有可能的路径)java

1条答案

相关问题

热门标签

最新问答