Wikiszótár

elárasztásos kitöltés

Magyar

Kiejtés

  • IPA: [ ˈɛlaːrɒstaːʃoʃkitølteːʃ]

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[x][y]
    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[0].méret:
        térj vissza
    ha grid[x][y] != old_color:
        térj vissza

    grid[x][y] = 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[0])
    old_color = grid[x][y]

    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[x][y] != old_color:
            return
        grid[x][y] = 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 = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
]

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

for row in result:
    print(row)

Kimenet: 

[2, 2, 2]
[2, 2, 0]
[2, 0, 1]

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[0].size();

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

    grid[x][y] = 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[x][y];
    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

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=elárasztásos_kitöltés&oldid=3479528”