from heapq import heappop, heappush
        from PIL import Image, ImageDraw
        import cv2
        import time

        #This maze solver algorithm works for mazes which have a border all around
        #itself. When there's an opening in the border, it won't work.

        #Path to maze
        mazeImage = "Maze.png"

        #Turning an image into a binary maze
        start_time = time.time()
        im = Image.open(mazeImage)
        width, height = im.size
        maze = list(im.getdata())
        for n, i in enumerate(maze):
            if i == (0, 0, 0) or i == (0, 0, 0, 255):
                maze[n] = 1
            else:
                maze[n] = 0
        maze = [maze[i * width:(i + 1) * width] for i in range(height)]

        def maze2graph(maze):
            #Converts the maze into a 2D array and then into a graph
            #For each node, it will look in which direction it is possible to go
            height = len(maze)
            width = len(maze[0]) if height else 0
            graph = {(i, j): [] for j in range(width) for i in range(height) if not maze[i][j]}
            for row, col in graph.keys():
                if row < height - 1 and not maze[row + 1][col]:
                    graph[(row, col)].append(("S", (row + 1, col)))
                    graph[(row + 1, col)].append(("N", (row, col)))
                if col < width - 1 and not maze[row][col + 1]:
                    graph[(row, col)].append(("E", (row, col + 1)))
                    graph[(row, col + 1)].append(("W", (row, col)))
            return graph

        def heuristic(cell, goal):
            #Manhattan distance heuristic
            return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])

        def astar(maze):
            img = cv2.imread(mazeImage, 1)
            #img = cv2.resize(img, (0,0), fx=3, fy=3)
            cv2.imshow(mazeImage, img)
            #Start coordinates
            start = (1, 1)
            #Goal coordinates
            goal = (len(maze) - 2, len(maze[0]) - 2)
            pr_queue = []
            heappush(pr_queue, (0 + heuristic(start, goal), 0, "", start))
            visited = set()
            graph = maze2graph(maze)
            while pr_queue:
                _, cost, path, current = heappop(pr_queue)
                if current == goal:
                    return path
                if current in visited:
                    continue
                visited.add(current)
                for direction, neighbour in graph[current]:
                    heappush(pr_queue, (cost + heuristic(neighbour, goal), cost + 1,
                                        path + direction, neighbour))
            return "There's no option to get to the end"

        def visualize_solution(maze):
            #Takes the solution and draws the path on the maze in a new png file
            img = Image.open(mazeImage)
            solution = astar(maze)
            draw = ImageDraw.Draw(img)
            start = (1, 1)
            cell = start
            line_color = (255,0,0)
            
            for i in range (len(solution)):
                if solution[i] == "S":
                    cell = tuple(map(sum,zip(start,(0,1))))
                    draw.line([start, cell], fill=line_color, width=1)
                    start = cell
                if solution[i] == "E":
                    cell = tuple(map(sum,zip(start,(1,0))))
                    draw.line([start, cell], fill=line_color, width=1)
                    start = cell
                if solution[i] == "N":
                    cell = tuple(map(sum,zip(start,(0,-1))))
                    draw.line([start, cell], fill=line_color, width=1)
                    start = cell
                if solution[i] == "W":
                    cell = tuple(map(sum,zip(start,(-1,0))))
                    draw.line([start, cell], fill=line_color, width=1)
                    start = cell
                    
            img.save("KenTummers_Solved_Maze.png")
            imgsol = cv2.imread("KenTummers_Solved_Maze.png", 1)
            #imgsol = cv2.resize(imgsol, (0,0), fx=3, fy=3)

            cv2.imshow("KenTummers_Solved_Maze.png", imgsol)
            cv2.waitKey(0)

        print("Directions per node:", maze2graph(maze))
        print("Maze:", maze)
        print("Path (N = North, E = East, S = South, W = West):",astar(maze))
        print("Total steps:", len(astar(maze)))
        end_time = time.time()
        print("Time:", end_time - start_time)
        visualize_solution(maze)