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!

z4qqq = [
    list("                               "),
    list("            xx   xx            "),
    list("       xxxx x xxx x xxxx       "),
    list("      xx  x x     x x  xx      "),
    list("    xxx  xx x     x xx  xxx    "),
    list("  xxx    x  x     x  x    xxx  "),
    list("  x      x  x     x  x      x  "),
    list(" xx       xx       xx       xx "),
    list(" x                           x "),
    list(" x                           x "),
    list(" x                           x "),
    list(" x                           x "),
    list(" x                           x "),
    list(" xx    xx             xx    xx "),
    list("  x   x  x xx     xx x  x   x  "),
    list("  xxx  x x x x   x x x x  xxx  "),
    list("    xx x xxx xx xx xxx x xx    "),
    list("     xxx      x x      xxx     "),
    list("              xxx              "),
    list("                               "),
]

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.

def kifest(kep, x, y):
    if y < 0 or x < 0 or y >= len(kep) or x >= len(kep[0]):
        return
    if kep[y][x] != ' ':
        return
    kep[y][x] = '.'
    kifest(kep, x, y - 1)
    kifest(kep, x, y + 1)
    kifest(kep, x - 1,y )
    kifest(kep, x + 1,y )

def main():
    z4qqq = [
        list("                               "),
        list("            xx   xx            "),
        list("       xxxx x xxx x xxxx       "),
        list("      xx  x x     x x  xx      "),
        list("    xxx  xx x     x xx  xxx    "),
        list("  xxx    x  x     x  x    xxx  "),
        list("  x      x  x     x  x      x  "),
        list(" xx       xx       xx       xx "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" x                           x "),
        list(" xx    xx             xx    xx "),
        list("  x   x  x xx     xx x  x   x  "),
        list("  xxx  x x x x   x x x x  xxx  "),
        list("    xx x xxx xx xx xxx x xx    "),
        list("     xxx      x x      xxx     "),
        list("              xxx              "),
        list("                               "),
    ]

    kifest(z4qqq, 10, 10);
    
    for sor in z4qqq:
        print("".join(sor))

main()