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

@Анонимус · Регистрация: 24.04.2009

Студворк — интернет-сервис помощи студентам

Как известно, если запускать волновой алгоритм на больших областях, то он захлебывется и умирает (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 секунд
Чёрт, погуглила, кажется всё придумано до меня..

@ostgals · 10.07.2009, 13:59

Не по теме:

Все равно, молодец! Настоящий программист :)

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@Анонимус 0 / 0 / 0 Регистрация: 24.04.2009 Сообщений: 16

	Волновой алгоритм на больших областях 06.07.2009, 02:37. Показов 1568. Ответов 1 Метки нет (Все метки) Как известно, если запускать волновой алгоритм на больших областях, то он захлебывется и умирает (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

@ostgals
	10.07.2009, 13:59
	Не по теме: Все равно, молодец! Настоящий программист :) 0

Опции темы