Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   www.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 08.02.2015, 11:47   #1
MoteX
Нуждающийся
 
Аватар для MoteX
 
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений
(для 8 пользователей)
Восклицание Алгоритм заливки массива

Добрый вечер. очередной вопрос от чайника программных дел.
Встал ребром вопрос о заливке массива. Гуглил много. Конечно так же долго читал вики, но так и не понял как это реализовывается.
Возможно кто нибудь подкинет статью или сам примерный алгоритм заливки массива по контуру.
Смысл такой: в массиве генерируется что то типа пещер, и есть места, которые не доступны из основной массы. Вот и нужно избавиться от них путем заливки и сравнения размеров полученных областей.
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
(Offline)
 
Ответить с цитированием
Старый 08.02.2015, 11:55   #2
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,217
Написано 436 полезных сообщений
(для 784 пользователей)
Ответ: Алгоритм заливки массива

ну, пусть в массиве 0 - пещера, (-1) - стена.

Перекрасим какую-нибудь из клеток со значением 0 в, например, 1.
И все клетки, которые =0 и соседние с 1, тоже будем перекрашивать в 1, пока они не кончатся.

Если останутся нулевые клетки - одну из них красим в цвет 2 и аналогично заливаем все, достижимые из неё.

И так до тех пор, пока не кончатся клетки со значением 0.

Потом пробежаться по всему массиву, поссчитать количество клеток с номерами 1, 2, ... - получим размеры областей
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
MoteX (08.02.2015)
Старый 08.02.2015, 12:06   #3
MoteX
Нуждающийся
 
Аватар для MoteX
 
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений
(для 8 пользователей)
Ответ: Алгоритм заливки массива

Так я и задумывал сделать, но не могу реализовать это в виде кода
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
(Offline)
 
Ответить с цитированием
Старый 08.02.2015, 12:35   #4
MoteX
Нуждающийся
 
Аватар для MoteX
 
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений
(для 8 пользователей)
Ответ: Алгоритм заливки массива

Похоже я понял как это сделать простым способом. Взял два цикла и закрашивал все что не заходило в стену - отлично работает и зачем тему создал
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
(Offline)
 
Ответить с цитированием
Старый 08.02.2015, 12:48   #5
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,217
Написано 436 полезных сообщений
(для 784 пользователей)
Ответ: Алгоритм заливки массива

Если забить на скорость выполнения:
пусть arr[] - массив длиной width*height, уже заполненный 0 и -1

//заполняет, говорит, сколько клеток изменил
int fill(int color){
int changed 0;
for(
int y=0y<heighty++)
    for(
int x=0x<widthx++)
        if (
arr[x+y*width]==color){
        
тут цикл по соседям (напримеру кого x и y отличаются на единицу)
        
для каждого соседа по координатам xnyn{
            if (
arr[xn width*yn]==0){
                 
arr[xn width*yn] = color;
                 
changed++;
             }
        }
    }
return 
changed
}

сам алгоритм
label
:
for(
int color1;;color++){   
    for(
int i=0i<width*heighti++)  //ищем необработанные клетки
        
if(arr[i]==0){
             
arr[i] = color//закрашиваем клетку
             
while(fill(color) != 0) {}//заполняем всех соседей, пока прогресс не прекратится
             
continue label// выпрыгиваем в главный цикл, чтобы красить следующим цветом
        
}
    break;  
//клеток не найдено, всё обработано. конец

Можно его очень сильно ускорить, но я писал так, чтобы было максимально понятно.
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
MoteX (08.02.2015)
Старый 08.02.2015, 13:11   #6
MoteX
Нуждающийся
 
Аватар для MoteX
 
Регистрация: 21.10.2009
Сообщений: 51
Написано 6 полезных сообщений
(для 8 пользователей)
Ответ: Алгоритм заливки массива

Спасибо Но я сделал по другому. Выбирается рандомная пустая точка в массиве, затем от нее все закрашивается и после этого сверяется размер закрашенных и не закрашенных. Если закрашенных меньше то все повторяется Скорость не особо нужна т.к. процесс выполняется один раз
__________________
(ьсипдоп утэ йатич ен,йенгиф йадартс ен
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +1, время: 02:46.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com