Обяснен алгоритъм за запълване на наводнения

Flood fill е алгоритъм, използван главно за определяне на ограничена област, свързана с даден възел в многоизмерен масив. Това е много подобно на инструмента за кофа в програмите за рисуване.

Най-подхождащата реализация на алгоритъма е базирана на стека рекурсивна функция и за това ще говорим по-нататък.

Как работи?

Проблемът е доста прост и обикновено следва следните стъпки:

  1. Заемете позицията на началната точка.
  2. Решете дали искате да отидете в 4 посоки ( N, S, W, E ) или 8 посоки ( N, S, W, E, NW, NE, SW, SE ).
  3. Изберете заместващ цвят и целеви цвят.
  4. Пътувайте в тези посоки.
  5. Ако плочката, върху която кацате, е цел, повторно я поставете с избрания цвят.
  6. Повторете 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).