Пояснено алгоритм заповнення потопом

Заповнення потопу - це алгоритм, який в основному використовується для визначення обмеженої області, підключеної до даного вузла в багатовимірному масиві. Це дуже схоже на інструмент відро в програмах фарбування.

Найбільш наближеною реалізацією алгоритму є рекурсивна функція на основі стеку, і про це ми поговоримо далі.

Як це працює?

Проблема досить проста і зазвичай виконується наступними кроками:

  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 - кількість острова з найбільшою площею.
  • А - площа 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).