import tkinter as tk
from queue import Queue

def create_grid(event=None):
    for i in range(15):
        for j in range(15):
            x1 = i * 20
            y1 = j * 20
            x2 = x1 + 20
            y2 = y1 + 20
            if (i == 0 and j == 0) or (i == 14 and j == 14):
                canvas.create_rectangle(x1, y1, x2, y2, fill="red", outline="black")
            elif grid[j][i] == 0:
                canvas.create_rectangle(x1, y1, x2, y2, fill="white", outline="black")
            else:
                canvas.create_rectangle(x1, y1, x2, y2, fill="black", outline="black")

def toggle_color(event):
    x = event.x // 20
    y = event.y // 20
    if (x == 0 and y == 0) or (x == 14 and y == 14):
        return
    if grid[y][x] == 0:
        grid[y][x] = 1
    else:
        grid[y][x] = 0
    create_grid()

def find_path():
    q = Queue()
    q.put((0, 0))
    visited = set()
    visited.add((0, 0))
    parent = {}

    while not q.empty():
        x, y = q.get()

        if (x, y) == (14, 14):
            path = []
            while (x, y) != (0, 0):
                path.append((x, y))
                x, y = parent[(x, y)]
            return path

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < 15 and 0 <= new_y < 15 and grid[new_y][new_x] == 0 and (new_x, new_y) not in visited:
                q.put((new_x, new_y))
                visited.add((new_x, new_y))
                parent[(new_x, new_y)] = (x, y)

    return []

def start_button_clicked():
    path = find_path()
    if path:
        for x, y in path:
            x1 = x * 20
            y1 = y * 20
            x2 = x1 + 20
            y2 = y1 + 20
            canvas.create_rectangle(x1, y1, x2, y2, fill="green", outline="black")
    else:
        print("No valid path found.")

root = tk.Tk()
root.title("Grid App")

canvas = tk.Canvas(root, width=300, height=300)
canvas.pack()

grid = [[0 for _ in range(15)] for _ in range(15)]

canvas.bind("<Button-1>", toggle_color)

create_grid()

start_button = tk.Button(root, text="Start", command=start_button_clicked)
start_button.pack()

root.mainloop()