我正在尝试编写一个递归方法,该方法将找到一条路径而不回溯到int矩阵中的某个位置,该位置包含值0,1 . 0可以踩,1不是 . 我也限制了一个超过50步的路径 .
位置是一个具有行和列值(x,y)的对象 . locationEquals是一个函数,如果两个Locations相同则返回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'为空,这意味着它没有找到方法 . 但是这个矩阵肯定有一种方法,所以这是我无法找到的代码中的错误 .
1 回答
问题是,每次进行递归的下一步时,您都不会创建新列表(您的临时变量不是临时变量,因为它只是对路径的引用而不是它的副本) .
为了解决这个问题,我用
List<Location> temp = new ArrayList<>(path);
替换了List<Location> temp = path;
所以代码是: