1

私はコードを持っています:

private void colorize(int color, int x, int y) {
    visited[x][y] = true;
    if (x + 1 < d)
        if (board[x + 1][y] == board[x][y] && visited[x + 1][y] == false)
            colorize(color, x + 1, y);
    if (x - 1 >= 0)
        if (board[x - 1][y] == board[x][y] && visited[x - 1][y] == false)
            colorize(color, x - 1, y);
    if (y + 1 < d)
        if (board[x][y + 1] == board[x][y] && visited[x][y + 1] == false)
            colorize(color, x, y + 1);
    if (y - 1 >= 0)
        if (board[x][y - 1] == board[x][y] && visited[x][y - 1] == false)
            colorize(color, x, y - 1);
    board[x][y] = color;
}

私はそれを呼びます: colorize(int random, int 0, int 0). これにより、小さなテーブル (20x20) でもスタックオーバーフローが発生します。再帰なしでこれを行うにはどうすればよいですか?

4

3 に答える 3

4

与えられたコードは問題ないようです。

何なのか疑問がありますが、d正解は正方形グリッドの幅だと思います。

これを呼び出すコードに問題がある可能性がありますが、指定したコードでスタックオーバーフローが発生することはありません。

MånsRolandiDanielssonの答えに基づいて、明示的なスタックを使用せず、ヒープ上にスタックを構築します。私のJavaは非常に錆びていますが、これは機能するはずです。誰かがこのコードの修正を持っている場合は、遠慮なく修正してください。

スタックオーバーフローを取得する代わりに、大きなテーブルサイズでは、java.lang.OutOfMemoryError: Java heap space代わりにエラーが発生します。おそらく、メモリ使用量を最適化するために、（リンクリストではなく）セットまたはその他のデータ構造を使用できます。

import java.util.Queue;
import java.util.LinkedList;

class Pair<L,R> {
    private L l;
    private R r;

    public Pair(L l, R r){
        this.l = l;
        this.r = r;
    }

    public L getL(){ return l; }
    public R getR(){ return r; }
}


public class HelloW {
    static int d = 20;
    static boolean[][] visited = new boolean[d][d];
    static int[][] board = new int[d][d];

    static Queue<Pair<Integer, Integer>> Q = new LinkedList<Pair<Integer, Integer>>();

    static void colorize(int color, int orig_x, int orig_y) {
        Q.add(new Pair<Integer, Integer>(orig_x, orig_y));

        while (Q.isEmpty() == false) {
            Pair<Integer,Integer> foo = Q.remove();
            int x = foo.getL();
            int y = foo.getR();
            int old_color = board[x][y];

            visited[x][y] = true;
            board[x][y]  = color;

            if (x + 1 < d)
                if (board[x + 1][y] == old_color && visited[x + 1][y] == false)
                    Q.add(new Pair<Integer, Integer>(x+1, y));
            if (x - 1 >= 0)
                if (board[x - 1][y] == old_color && visited[x - 1][y] == false)
                    Q.add(new Pair<Integer, Integer>(x-1, y));
            if (y + 1 < d)
                if (board[x][y + 1] == old_color && visited[x][y + 1] == false)
                    Q.add(new Pair<Integer, Integer>(x, y+1));
            if (y - 1 >= 0)
                if (board[x][y - 1] == old_color && visited[x][y - 1] == false)
                    Q.add(new Pair<Integer, Integer>(x, y-1));
        }
    }

    public static void main (String[] args) {
        colorize(1, 0, 0);
    }
}
于 2012-11-08T23:11:16.390 に答える
1

私はあなたのコードをコピーして、以下に示すように実行しました。完璧に動作し、「true」でいっぱいのマトリックスと1でいっぱいのマトリックスになります。

static int d = 20;
static boolean[][] visited = new boolean[d][d];
static int[][] board = new int[d][d];

static void colorize(int color, int x, int y) {
    visited[x][y] = true;
    if (x + 1 < d)
        if (board[x + 1][y] == board[x][y] && visited[x + 1][y] == false)
            colorize(color, x + 1, y);
    if (x - 1 >= 0)
        if (board[x - 1][y] == board[x][y] && visited[x - 1][y] == false)
            colorize(color, x - 1, y);
    if (y + 1 < d)
        if (board[x][y + 1] == board[x][y] && visited[x][y + 1] == false)
            colorize(color, x, y + 1);
    if (y - 1 >= 0)
        if (board[x][y - 1] == board[x][y] && visited[x][y - 1] == false)
            colorize(color, x, y - 1);
    board[x][y] = color;
}

public static void main(String[] args)
{
    colorize(1, 0, 0);
}

編集: テスト プログラムは私のコンピューターで d = 20 に対して正常に動作しますが、d = 100 に増やすと StackOverflow が発生します。アルゴリズムは多かれ少なかれ問題ないようですが、再帰は不必要に深くなり、より洗練された定式化が必要です。

于 2012-11-08T23:13:40.697 に答える
0

私が知る限り、あなたのコードは正しく機能します。それに影響を与える可能性がある唯一のことは、再帰中に別のスレッドが来てデータ構造の1つを変更した場合、または投稿する前にデータ構造を過度に単純化した場合です。

于 2012-11-08T23:15:27.127 に答える