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），这也给了我stackoverflow。我怎么能在没有递归的情况下做到这一点？

4

3 回答 3

4

给出的代码似乎很好。

关于什么是一个问题d，但我假设它是正确的方形网格的宽度。

无论代码调用它，您都可能遇到问题，但是您给我们的代码不应该有堆栈溢出。

根据 Måns Rolandi Danielsson 的回答，这里有一个不使用显式堆栈，而是在堆上构建一个。我的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

我刚刚复制了您的代码并像您在下面看到的那样运行它，它运行良好，最终得到一个充满“真”的矩阵和一个充满“真”的矩阵：

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

据我所知，您的代码可以正常工作；唯一可能影响它的是，如果另一个线程在递归期间出现并修改了您的一个数据结构，或者您在发布之前过度简化了它。

于 2012-11-08T23:15:27.127 回答