Проблемы рекурсивного массива

Question

У меня возникли проблемы с переполнением стека, и, надеюсь, кто-нибудь подскажет мне не / нерекурсивное решение.

Ident[][] map = ...

private int explore(Ident item, int xcoord, int ycoord) {
    if ((map[xcoord][ycoord] == null) || !map[xcoord][ycoord].equals(item))
             return 0;

    map[xcoord][ycoord] = null;
    int sumX, sumY, counter = 1;
    item.translate(xcoord, ycoord);

    for (int y = -1; y <= 1; y++)
        for (int x = -1; x <= 1; x++) {
             sumX = x + xcoord;
             sumY = y + ycoord;
            if (((y != 0) || (x != 0)) && (sumX >= 0) && (sumX < map.length) && 
                     (sumY >= 0) && (sumY < map.[0].length))
                     counter += explore(item, sumX, sumY);
             }
        }
    }
    return counter;
}

Этот метод получает 2-мерный массив Ident Objects, целевой Ident и начальную позицию в массиве. Рекурсивно пересекает массив считая, насколько большой из непрерывной области занимает Идент. Он также центрирует введенный элемент Ident в центре области.

Зацикливая массив карт и вызывая метод explore для любых ненулевых элементов, я могу создать массив элементов Ident с центром в их областях и с размерами относительно их областей.

Видно, что с любыми картами, кроме маленьких, стек переполняется.

У кого-нибудь есть альтернативный метод выполнения той же задачи? Или какое-то понимание, чтобы помочь мне найти его?

Answer 1

Чтобы исключить рекурсию, составьте список координат для исследования и зациклите, пока он содержит какие-либо элементы; в вашем цикле создайте новый список координат для исследования и в конце цикла замените старый список новым списком.

Answer 2

Это возвращает меня к середине 80-х. Любой алгоритм заливки требует определенного количества состояний. Я, к сожалению, не помню алгоритмы. То, что эффективно для большого пространства, вероятно, не будет эффективным для лабиринта.

Чтобы избежать рекурсии, вместо рекурсии просто добавьте данные, которые вы бы назвали, в стек. Зацикливайтесь на выталкивании следующей неисследованной координаты с вершины стека. Использование стека, а не очереди FIFO немного улучшает локальность, хотя это, вероятно, не будет иметь большого значения здесь.

private int explore(Ident item, int xcoord, int ycoord) {
    int counter = 0;

    Queue<Point> stack = Collections.asLifoQueue(new ArrayDeque<Point>());
    stack.add(new Point(xcoord, ycoord));

    while (!stack.isEmpty()) {
        Point point = stack.remove();
        xcoord = point.x;
        ycoord = point.y;

        if (!item.equals(map[xcoord][ycoord])) {
            continue;
        }

        ++counter;
        map[xcoord][ycoord] = null;
        item.translate(xcoord, ycoord);

        for (int y = -1; y <= 1; y++)
            for (int x = -1; x <= 1; x++) {
                 int sumX = x + xcoord;
                 int sumY = y + ycoord;
                 if (
                     !(x == 0 && y == 0) &&
                     0 <= sumX && sumX < map.length &&
                     0 <= sumY && sumY < map[0].length
                 ) {
                     stack.add(new Point(sumX, sumY));
                 }
            }
        }
    }
    return counter;
}

В лучших традициях stackoverflow такого еще не видел компилятор. (Он также сохраняет большую часть оригинального алгоритма.)