forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Алгоритм заливки массива (http://forum.boolean.name/showthread.php?t=19680)

MoteX 08.02.2015 14:47
Алгоритм заливки массива
 
Добрый вечер. очередной вопрос от чайника программных дел.
Встал ребром вопрос о заливке массива. Гуглил много. Конечно так же долго читал вики, но так и не понял как это реализовывается.
Возможно кто нибудь подкинет статью или сам примерный алгоритм заливки массива по контуру.
Смысл такой: в массиве генерируется что то типа пещер, и есть места, которые не доступны из основной массы. Вот и нужно избавиться от них путем заливки и сравнения размеров полученных областей.

Igor 08.02.2015 14:55
Ответ: Алгоритм заливки массива
 
ну, пусть в массиве 0 - пещера, (-1) - стена.

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

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

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

Потом пробежаться по всему массиву, поссчитать количество клеток с номерами 1, 2, ... - получим размеры областей

MoteX 08.02.2015 15:06
Ответ: Алгоритм заливки массива
 
Так я и задумывал сделать, но не могу реализовать это в виде кода :)

MoteX 08.02.2015 15:35
Ответ: Алгоритм заливки массива
 
Похоже я понял как это сделать простым способом. Взял два цикла и закрашивал все что не заходило в стену - отлично работает:) и зачем тему создал :dontknow:

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

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

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

MoteX 08.02.2015 16:11
Ответ: Алгоритм заливки массива
 
Спасибо :) Но я сделал по другому. Выбирается рандомная пустая точка в массиве, затем от нее все закрашивается и после этого сверяется размер закрашенных и не закрашенных. Если закрашенных меньше то все повторяется :)Скорость не особо нужна т.к. процесс выполняется один раз


Часовой пояс GMT +4, время: 10:26.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot