再帰的なスタックオーバーフローと奇数オブジェクトの参照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));の直後にprintステートメントを入れて、再帰的メソッド内にpath.size()を印刷すると、サイズのシーケンスが一貫して印刷されない（1,2,3,4,2,3,4）、なぜですか？あなたは再帰を行っている方法が間違っている...

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

を

UPDATE

はこのようにそれを修正し、それはまだスタックオーバーフローを刺激します。再帰的なメソッドを作成する際には、それぞれの呼び出しが前の呼び出しをスタックに置きます。あなたが再帰を永遠に実行している場合は、スタックオーバーフローが発生するほど深く進むためにスタックに十分な空きがないでしょう。

ここに問題があります。あなたは訪問されたことを毎回マークしていません。これがあなたのグリッドだと想像してみてください。引用符で囲まれたセルは、我々の方法

"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)です。したがって、無限のメソッド呼び出しをスタックに配置します。

ソリューション

は、細胞が訪問し、訪問したとして、あなたがセルマークにそれを行くようにされているものと方法に別の配列を渡します。これにより、あなたが以前に見たことに戻ることを避けることができます