Алгоритм заливки массива
Добрый вечер. очередной вопрос от чайника программных дел.
Встал ребром вопрос о заливке массива. Гуглил много. Конечно так же долго читал вики, но так и не понял как это реализовывается. Возможно кто нибудь подкинет статью или сам примерный алгоритм заливки массива по контуру. Смысл такой: в массиве генерируется что то типа пещер, и есть места, которые не доступны из основной массы. Вот и нужно избавиться от них путем заливки и сравнения размеров полученных областей. |
Ответ: Алгоритм заливки массива
ну, пусть в массиве 0 - пещера, (-1) - стена.
Перекрасим какую-нибудь из клеток со значением 0 в, например, 1. И все клетки, которые =0 и соседние с 1, тоже будем перекрашивать в 1, пока они не кончатся. Если останутся нулевые клетки - одну из них красим в цвет 2 и аналогично заливаем все, достижимые из неё. И так до тех пор, пока не кончатся клетки со значением 0. Потом пробежаться по всему массиву, поссчитать количество клеток с номерами 1, 2, ... - получим размеры областей |
Ответ: Алгоритм заливки массива
Так я и задумывал сделать, но не могу реализовать это в виде кода :)
|
Ответ: Алгоритм заливки массива
Похоже я понял как это сделать простым способом. Взял два цикла и закрашивал все что не заходило в стену - отлично работает:) и зачем тему создал :dontknow:
|
Ответ: Алгоритм заливки массива
Если забить на скорость выполнения:
пусть arr[] - массив длиной width*height, уже заполненный 0 и -1 PHP код:
|
Ответ: Алгоритм заливки массива
Спасибо :) Но я сделал по другому. Выбирается рандомная пустая точка в массиве, затем от нее все закрашивается и после этого сверяется размер закрашенных и не закрашенных. Если закрашенных меньше то все повторяется :)Скорость не особо нужна т.к. процесс выполняется один раз
|
Часовой пояс GMT +4, время: 19:40. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot