elárasztásos kitöltés

Üdvözlöm, Ön a elárasztásos kitöltés szó jelentését keresi. A DICTIOUS-ban nem csak a elárasztásos kitöltés szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a elárasztásos kitöltés szót egyes és többes számban mondani. Minden, amit a elárasztásos kitöltés szóról tudni kell, itt található. A elárasztásos kitöltés szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Aelárasztásos kitöltés és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Magyar

Kiejtés

  • IPA:

Főnév

elárasztásos kitöltés

  1. (matematika, algoritmusok) Az elárasztásos kitöltés egy algoritmus, amelyet gyakran alkalmaznak képfeldolgozásban vagy játékfejlesztésben arra, hogy egy összefüggő területet egy adott mintázattal vagy színnel kitöltsön. Az algoritmus hasonlóan működik, mint a festékesvödör eszköz grafikai programokban.


Probléma leírása

Bemenet:

  • Egy kétdimenziós mátrix ((grid)), ahol minden elem egy adott szín vagy érték.
  • Egy kezdőpozíció ((x, y)).
  • Egy kitöltési szín ((new_color)).

Kimenet:

A mátrix, ahol az összes kezdőpozícióval szomszédos és azonos színű elem helyett a kitöltési szín található.


Algoritmus működése

  1. Indítás:
    • Határozzuk meg a kezdőpozíció színét ((old_color)).
    • Ha az (old_color) megegyezik a (new_color)-ral, a kitöltés már kész.
  2. Rekurzív vagy iteratív eljárás:
    • Haladjunk minden irányba ((fel, le, balra, jobbra)).
    • Minden olyan cellát, amely az (old_color)-ral egyezik, cseréljünk (new_color)-ra.
    • Folytassuk az eljárást az új cellák szomszédaira.
  3. Leállás:
    • Ha nincs több szomszédos cella, amely az (old_color)-ral egyezik, a kitöltés kész.


Időkomplexitás

  • Legrosszabb eset: (O(n m)), ahol (n) és (m) a mátrix méretei.
  • Az algoritmus minden cellát legfeljebb egyszer meglátogat.


Pszeudokód

FloodFill(grid, x, y, new_color):
    old_color = grid
    ha old_color == new_color:
        térj vissza

    FloodFillUtil(grid, x, y, old_color, new_color)

FloodFillUtil(grid, x, y, old_color, new_color):
    ha x < 0 vagy x >= grid.méret vagy y < 0 vagy y >= grid.méret:
        térj vissza
    ha grid != old_color:
        térj vissza

    grid = new_color

    FloodFillUtil(grid, x+1, y, old_color, new_color)
    FloodFillUtil(grid, x-1, y, old_color, new_color)
    FloodFillUtil(grid, x, y+1, old_color, new_color)
    FloodFillUtil(grid, x, y-1, old_color, new_color)

Python implementáció

def flood_fill(grid, x, y, new_color):
    rows, cols = len(grid), len(grid)
    old_color = grid

    if old_color == new_color:
        return grid

    def fill(x, y):
        if x < 0 or x >= rows or y < 0 or y >= cols or grid != old_color:
            return
        grid = new_color
        fill(x + 1, y)
        fill(x - 1, y)
        fill(x, y + 1)
        fill(x, y - 1)

    fill(x, y)
    return grid

# Példa használat
grid = [
    ,
    ,
    
]

x, y = 1, 1
new_color = 2
result = flood_fill(grid, x, y, new_color)

for row in result:
    print(row)

Kimenet:

C++ implementáció

#include <iostream>
#include <vector>
using namespace std;

void floodFillUtil(vector<vector<int>>& grid, int x, int y, int oldColor, int newColor) {
    int rows = grid.size();
    int cols = grid.size();

    if (x < 0 || x >= rows || y < 0 || y >= cols || grid != oldColor) {
        return;
    }

    grid = newColor;

    floodFillUtil(grid, x + 1, y, oldColor, newColor);
    floodFillUtil(grid, x - 1, y, oldColor, newColor);
    floodFillUtil(grid, x, y + 1, oldColor, newColor);
    floodFillUtil(grid, x, y - 1, oldColor, newColor);
}

void floodFill(vector<vector<int>>& grid, int x, int y, int newColor) {
    int oldColor = grid;
    if (oldColor != newColor) {
        floodFillUtil(grid, x, y, oldColor, newColor);
    }
}

int main() {
    vector<vector<int>> grid = {
        {1, 1, 1},
        {1, 1, 0},
        {1, 0, 1}
    };

    int x = 1, y = 1, newColor = 2;

    floodFill(grid, x, y, newColor);

    cout << "Kitöltött mátrix:" << endl;
    for (const auto& row : grid) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    return 0;
}

Kimenet: 

Kitöltött mátrix:
2 2 2
2 2 0
2 0 1

Összegzés

Előnyök:

  1. Egyszerű és hatékony algoritmus.
  2. Könnyen implementálható.

Hátrányok:

  1. Rekurzió használata mély mátrixoknál verem túlcsorduláshoz vezethet (helyette iteratív megoldás ajánlott).
  2. Csak szomszédos cellákra terjed ki; diagonális kitöltéshez módosítani kell az irányokat.

Az elárasztásos kitöltés egy alapvető algoritmus, amely képfeldolgozásban, játékmenet-szimulációkban és térképi alkalmazásokban gyakran előfordul.


Fordítások

Tartalom

További információk

Enciclo
Wikious
Sapientia
Scientia
Boobota
Anandapedia
Sagapedia
Wikithot