# floodfill.py
#
# MIT-License
#
# Copyright © 2023, 2024 Theo van Haandel  py39@x4a.nl
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.

# versie 1.0  2023-10-19
#  floodfillR met recursie

# versie 1.1  2024-01-04
#  erbij niet recursieve
#   floodfillQ met queue en
#   floodfillS met stack

# zie ook https://en.wikipedia.org/wiki/Flood_fill
# en https://nl.wikipedia.org/wiki/Floodfill-algoritme

canvas = (
    list('.........................................'),
    list('............................xxxxxxx......'),
    list('.....xxxxxxxxxxxxxxxxxxxxxxx......x......'),
    list('.....x............................x......'),
    list('...xxx.........xxxxxxx...xxxxx....x......'),
    list('...x...........x.....x...x...x....x......'),
    list('...x.xxxx......x.....x...x...x....x...x..'),
    list('...x.x..x......x.....xxxxxxxxxxxxxx..x.x.'),
    list('...x.xx.x......x.....................x.x.'),
    list('...x....x......xxxxxxxxxxxxxxxxxxxxxx..x.'),
    list('...xxxxxx..............................x.'),
    list('.........xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.'),
    )

canvas2 = (
    list('....'),
    list('xxx.'),
    list('...x'),
    list('....'),
    )

fromChr = '.'
# fromChr = 'x'
toChr = 'o'

width = len(canvas[0])
height = len(canvas)

def printCanvas():
    for line in canvas:
        print(''.join(line))
    print()

def floodfillR(x, y):
    if 0 <= x < width and 0 <= y < height:
        if canvas[y][x] == fromChr:
            canvas[y][x] = toChr
            # printCanvas()
            floodfillR(x - 1, y)
            floodfillR(x + 1, y)
            floodfillR(x, y - 1)
            floodfillR(x, y + 1)

def floodfillQ(x, y):
    q = [ (x, y) ]
    while q:
        x, y = q.pop(0)
        if canvas[y][x] == fromChr:
            canvas[y][x] = toChr
            # printCanvas()
            q.append( (x - 1, y) )
            q.append( (x + 1, y) )
            q.append( (x, y - 1) )
            q.append( (x, y + 1) )

def floodfillS(x, y):
    s = [ (x, y) ]
    while s:
        x, y = s.pop() # s.pop(-1)
        if canvas[y][x] == fromChr:
            canvas[y][x] = toChr
            # printCanvas()
            s.append( (x - 1, y) )
            s.append( (x + 1, y) )
            s.append( (x, y - 1) )
            s.append( (x, y + 1) )

printCanvas()

floodfillR(10, 6)
# floodfillR(0, 0)

# floodfillQ(10, 6)
# floodfillS(10, 6)

printCanvas()
