Zárt terület kifestése

Szinte mindegyik rajzolóprogram tartalmazza a zárt terület kifestése eszközt, amellyel egy összefüggő területet tudunk valamilyen színűre festeni. Angolul meg szoktuk különböztetni a „flood fill” és a „boundary fill” algoritmust, de nagy elvi különbség nincsen a kettő között valójában. Az előbbi egy összefüggő, adott színű területet színez át, vagyis mindig csak ugyanarra a színre lép. Az utóbbi pedig egy körvonal által körbehatárolt területet színez be.

A két algoritmust innentől lényegileg egynek tekintjük, hiszen sejthető, hogy csak valamelyik elágazás feltételében térnek el egymástól: szín == sárga az egyik, szín != fekete a másik esetben.

A feladat tehát a következő. Adott egy két dimenziós tömb, amelyik egy képet reprezentál. A képen egy adott színnel el van kerítve egy terület – vagyis meg van rajzolva egy alakzat. Színezzük ki ennek az alakzatnak a belsejét! Az alakzat lehet konkáv is, abban az esetben is be kell menni minden zugba!

char z4qqq[20][32] = {
    "                               ",
    "            xx   xx            ",
    "       xxxx x xxx x xxxx       ",
    "      xx  x x     x x  xx      ",
    "    xxx  xx x     x xx  xxx    ",
    "  xxx    x  x     x  x    xxx  ",
    "  x      x  x     x  x      x  ",
    " xx       xx       xx       xx ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " x                           x ",
    " xx    xx             xx    xx ",
    "  x   x  x xx     xx x  x   x  ",
    "  xxx  x x x x   x x x x  xxx  ",
    "    xx x xxx xx xx xxx x xx    ",
    "     xxx      x x      xxx     ",
    "              xxx              ",
    "                               "
};

A rekurzió nélkül lehetetlennek tűnő feladat rekurzív megoldása végtelenül egyszerű. A függvény először megvizsgálja, hogy olyan pozíciót kapott-e, ahova szabad lépni, és amit ki kell festeni. Ha olyan pozícióról van szó, ami kilóg a képről; vagy nem szóköz van az adott helyen (már ki van festve), akkor egyből vissza is tér. Ha viszont kifestendő a pont, akkor kifesti, és kifesti a szomszédait is. A szomszédoknál ugyanez a feladat: az aktuális pontot kifesteni, és mind a négy irányba megpróbálni menni. Ha a festés ilyen módon végül egy zsákutcában elakad, a függvények visszatérnek – és a próbálkozás megy tovább a másik három lehetséges irányba. Zsákutca pedig a saját maga által kifestett pontok miatt is keletkezhet, hiszen onnantól kezdve, hogy egy pontot kifest az algoritmus, az ugyanolyan falnak számít, mint az eredeti alakzat körvonalai.

#include <stdio.h>

void kifest(char kep[20][32], int y, int x) {
    if (y < 0 || x < 0 || y >= 20 || x >= 31)
        return;
    if (kep[y][x] != ' ')
        return;
    kep[y][x] = '.';
    kifest(kep, y - 1, x);
    kifest(kep, y + 1, x);
    kifest(kep, y, x - 1);
    kifest(kep, y, x + 1);
}

int main(void) {
    char z4qqq[20][32] = {
        "                               ",
        "            xx   xx            ",
        "       xxxx x xxx x xxxx       ",
        "      xx  x x     x x  xx      ",
        "    xxx  xx x     x xx  xxx    ",
        "  xxx    x  x     x  x    xxx  ",
        "  x      x  x     x  x      x  ",
        " xx       xx       xx       xx ",
        " x                           x ",
        " x                           x ",
        " x                           x ",
        " x                           x ",
        " x                           x ",
        " xx    xx             xx    xx ",
        "  x   x  x xx     xx x  x   x  ",
        "  xxx  x x x x   x x x x  xxx  ",
        "    xx x xxx xx xx xxx x xx    ",
        "     xxx      x x      xxx     ",
        "              xxx              ",
        "                               "
    };

    kifest(z4qqq, 10, 10);
    
    for (int y = 0; y < 20; ++y)
        puts(z4qqq[y]);

    return 0;
}