Волновой алгоритм на больших областях

Как известно, если запускать волновой алгоритм на больших областях, то он захлебывется и умирает (StackOverflow). Однако, например, стандартный floodfill из paint'a работает на них и справляется относительно быстро. В чем хитрость?

Добавлено через 5 часов 57 минут 49 секунд
Немного попыхтев, придумала простой способ, он быстрее, не захлебывается и работает без рекурсии (может, кому-то пригодится):
0. Берём координаты начальной точки работы алгоритма за x и y.
1. Создаём список клеток A[], требующих посещения. Элементы списка будут координатами.
2. Создаём карту (двухмерный массив) препятствий B[][], пройденных клеток и клеток, проход которых запланирован в списке. Будем обозначать непройденные клетки, свободные для прохождения 0, те, что запланированы в списке A[] -- 1, те, что уже пройдены -- 2, а те, что содержат препятствия -- -1.
3. Длина списка будет храниться в переменной M, её начальное значение 1. А первой и единственной записью в списке является точка с координатами (x, y).
4. Будем выполнять цикл, пока список клеток не станет "пустым", т.е. пока M>0.
(Далее описание цикла. Обрабатывается только та точка, которая стоит первой в списке)
5. Обозначаем на вспомогательной карте, что первую точку мы обошли. Т.е. B[A[0]x][A[0]y]=2.
6. Запоминаем координаты этой точки, как X1 и Y1
7. Удаляем её из списка (А именно, M--; B[0]x=B[M]x; B[0]y=B[M]y).
8. По возможности готовим к проходу соседние клетки:
1) Проверяем, не заходят ли координаты соседней клетки за границы массива
2) Проверяем, не состоит ли клетка в списке уже запланированных и не является ли препятствием, т.е. на карте B[][] эта клетка должна быть с нулем (возможно, еще какие-нибудь условия, но это уже частности).
9. Если условия соблюдаются, то записываем клетку в список (соотв., M++) и отмечаем на карте, как запланированную.

Алгоритм справляется с более крупными областями, чем рекурсия, т.к. после вызова подфункций, рекурсия "не умирает".

Добавлено через 19 минут 16 секунд
Чёрт, погуглила, кажется всё придумано до меня..

0

0