Flood fill е алгоритъм, използван главно за определяне на ограничена област, свързана с даден възел в многоизмерен масив. Това е много подобно на инструмента за кофа в програмите за рисуване.
Най-подхождащата реализация на алгоритъма е базирана на стека рекурсивна функция и за това ще говорим по-нататък.
Как работи?
Проблемът е доста прост и обикновено следва следните стъпки:
- Заемете позицията на началната точка.
- Решете дали искате да отидете в 4 посоки ( N, S, W, E ) или 8 посоки ( N, S, W, E, NW, NE, SW, SE ).
- Изберете заместващ цвят и целеви цвят.
- Пътувайте в тези посоки.
- Ако плочката, върху която кацате, е цел, повторно я поставете с избрания цвят.
- Повторете 4 и 5, докато не сте били навсякъде в границите.
Нека вземем за пример следния масив:
Червеният квадрат е началната точка, а сивите квадрати са така наречените стени.
За повече подробности, ето част от кода, описваща функцията:
int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) Както се вижда по-горе, моята отправна точка е (4,4). След извикване на функцията за началните координати x = 4 и y = 4 , мога да започна да проверявам дали на място няма стена или цвят. Ако това е валидно, маркирам мястото с един „цвят“ и започвам да проверявам останалите квадрати.
Отивайки на юг, ще стигнем до точка (5,4) и функцията работи отново.
Проблем с упражненията
Винаги съм смятал, че решаването на (или повече) проблеми / и с помощта на новоучен алгоритъм е най-добрият начин за пълно разбиране на концепцията.
Ето едно:
Изявление:
В двумерен масив ви се дава n брой „острови“ . Опитайте се да намерите най-голямата площ на остров и съответния номер на острова. 0 маркира вода и всеки друг x между 1 и n отбелязва един квадрат от повърхността, съответстваща на остров x.
Вход
- n - броят на островите.
- l, c - размерите на матрицата.
- следващите l редове, c числа, даващи l -тия ред на матрицата.
Изход
- i - броят на острова с най-голяма площ.
- A - площта на i -тия остров.
Пример:
Имате следния вход:
2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2За което ще получите остров №. 2 като най-големият остров с площ от 5 квадрата.
Съвети
Проблемът е доста лесен, но ето няколко съвета:
1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).