from PIL import Image

image = Image.open("lab1.png")

# Trouver le noeud de départ
x = 0
y = 0
while image.getpixel((x, y)) != (255, 255, 255):
    x += 1

def voisins_non_visites():
    res = []
    for vx, vy in [(x, y + 1), (x + 1, y), (x - 1, y), (x, y - 1)]:
        if 0 <= vx < image.width and 0 <= vy < image.height:
            if image.getpixel((vx, vy)) == (255, 255, 255):
                res.append((vx, vy))
    return res

image.putpixel((x, y), (128, 128, 128))

chemin = []

while y != image.height - 1:
    voisins = voisins_non_visites()
    if not voisins:
        x, y = chemin.pop()
    else:
        vx, vy = voisins[0]
        chemin.append((x, y))
        image.putpixel((vx, vy), (128, 128, 128))
        x, y = vx, vy

chemin.append((x, y))

for nx, ny in chemin:
    image.putpixel((nx, ny), (255, 0, 0))

image.save("lab1-solved.png")