递归堆栈溢出和奇数对象参考Java

Question

private boolean[][] computeMainOutline(boolean[][] outline) { 

    int pixelValue[][] = new int [width][height]; 

    for(int x = 0; x < width; x++) 
     for(int y = 0; y < height; y++) 
      if(pixelValue[x][y] == 0) { 
      ArrayList<Point2D.Double> path = new ArrayList<>(); 
      findPath(x, y, outline, pixelValue, path); 
      } 
    return new boolean[1][1]; // to avoid compilation error 
} 

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path) { 
    path.add(new Point2D.Double(x, y)); 

    if(x > 0 && outline[x - 1][y] == true) // check right 
     findPath(x - 1, y, outline, pixelValue, path); 
    if(x < width && outline[x + 1][y] == true) // check left 
     findPath(x + 1, y, outline, pixelValue, path); 
    if(y < height && outline[x][y + 1] == true) // check up 
     findPath(x, y + 1, outline, pixelValue, path); 
    if(y > 0 && outline[x][y - 1] == true) // check down 
     findPath(x, y - 1, outline, pixelValue, path); 
} 

上述方法给出StackOverflowError，我不知道为什么。

方法computeMainOutline遍历整个outline数组和pixelValue数组，这两个数组的大小相同。如果没有为特定坐标计算“值”，那么findPath函数将递归地计算路径。路径基本上是多少个“真”数组元素彼此相邻。计算值的方法没有添加，但我的第一个问题是找到路径。

此外，如果我在path.add(new Point2D.Double(x, y));之后立即打印path.add(new Point2D.Double(x, y));打印path.size()内部的递归方法，大小顺序不一致它可能会打印（1,2,3,4,2,3,4），为什么？

UPDATE

更正像这样，但它仍然会引发一个堆栈溢出...

private boolean[][] computeMainOutline(boolean[][] outline) { 

    int pixelValue[][] = new int [width][height]; 
    boolean visited[][] = new boolean[width][height]; 

    for(int x = 0; x < width; x++) 
     for(int y = 0; y < height; y++) 
      if(visited[x][y] == false) { 
      ArrayList<Point2D.Double> path = new ArrayList<>(); 
      findPath(x, y, outline, pixelValue, path, visited); 
      } 
    return new boolean[1][1]; // to avoid compilation error 
} 

private void findPath(int x, int y, boolean[][] outline, int pixelValue [][], ArrayList<Point2D.Double> path, boolean visited [][]) { 
    path.add(new Point2D.Double(x, y)); 
    visited[x][y] = true; 

    if(x > 0 && visited[x - 1][y] == false && outline[x - 1][y] == true) // check right 
     findPath(x - 1, y, outline, pixelValue, path, visited); 
    if(x < width - 1 &&visited[x + 1][y] == false && outline[x + 1][y] == true) // check left 
     findPath(x + 1, y, outline, pixelValue, path, visited); 
    if(y < height - 1 && visited[x][y + 1] == false && outline[x][y + 1] == true) // check up 
     findPath(x, y + 1, outline, pixelValue, path, visited); 
    if(y > 0 && visited[x][y - 1] == false && outline[x][y - 1] == true) // check down 
     findPath(x, y - 1, outline, pixelValue, path, visited); 
} 

Answer 1

你做你的递归的方式是错误的。在进行递归方法的同时，每次调用都将先前的调用放在堆栈上。如果你是递归运行，那么堆栈中没有足够的空间去更深一层，导致堆栈溢出。

这是问题所在。您没有在每个时间步骤标记访问过的内容。想象一下，这是你的网格。引号中的细胞是我们的方法

"T" F F     T F F    "T" F F 
T F F (next step) "T" F F (next)  T F F 
T F F     T F F    T F F 

它可以追溯到它已经访问过的国家的(x,y)。因此，您将在堆栈中放入无限的方法调用。

解决方案

传递另一个数组与已经访问过的细胞的方法，当你去一个细胞将其标记为参观。这可以避免你回到之前看过的东西