Árvízkitöltési algoritmus magyarázata

Programozás

Az árvíz kitöltése olyan algoritmus, amelyet főleg egy adott csomóponthoz kötött, korlátozott terület meghatározására használnak egy többdimenziós tömbben. Szoros hasonlóság a festékprogramok vödör eszközével.

Az algoritmus legközelebb álló megvalósítása egy verem alapú rekurzív függvény, erről fogunk beszélni a továbbiakban.

Hogyan működik?

A probléma elég egyszerű, és általában a következő lépéseket követi:

  1. Vegyük a kiindulópont helyzetét.
  2. Döntse el, hogy 4 irányba ( É, D, NY, K ) vagy 8 irányba ( É, D, NY, K, ÉNy, ÉK, DK, DK ) szeretne-e menni .
  3. Válasszon egy helyettesítő színt és egy célszínt.
  4. Utazás ezekben az irányokban.
  5. Ha a csempe, amelyre landol, célpont, töltse fel újra a választott színnel.
  6. Ismételje meg a 4. és az 5. pontot, amíg mindenhol a határokon belül van.

Vegyük példának a következő tömböt:

alt szöveg

A piros négyzet a kiinduló pont, a szürke négyzetek pedig az úgynevezett falak.

További részletekért íme egy darab kód, amely leírja a függvényt:

int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color)

Mint fent látható, a kiindulópontom a (4,4). Miután meghívtam az x = 4 és y = 4 startkoordináták függvényét , elkezdhetem ellenőrizni, hogy nincs-e fal vagy szín a helyszínen. Ha ez érvényes, jelölje meg a helyet egy „színnel”, és kezdje el ellenőrizni a többi szomszédos négyzetet.

Dél felé haladva eljutunk az (5,4) ponthoz, és a függvény újra fut.

Gyakorlási probléma

Mindig úgy gondoltam, hogy egy (vagy több) probléma (k) megoldása egy újonnan megtanult algoritmus segítségével a koncepció teljes megértésének legjobb módja.

Tehát itt van egy:

Nyilatkozat:

Egy kétdimenziós tömbben n számú „szigetet” kap . Próbálja meg megtalálni egy sziget legnagyobb területét és a hozzá tartozó szigetszámot. 0 jelöli a vizet, és bármely más x 1 és n között egy négyzetet jelöl az x szigetnek megfelelő felszíntől.

Bemenet

  • n - a szigetek száma.
  • l, c - a mátrix méretei.
  • A következő L vonalak, c számok így a l edik sorának a mátrix.

Kimenet

  • i - a legnagyobb területtel rendelkező sziget száma.
  • A - az i . Sziget területe.

Volt:

A következő bemenet van:

2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2

Amiért megkapja a Nr. 2, mint a legnagyobb sziget, 5 négyzet területtel.

Tippek

A probléma meglehetősen egyszerű, de íme néhány tipp:

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).