# runtime
    # O( G(V,E) * Removable walls)
    # =
    # O(N*(|V|+|E|))  if N ~ removable walls

    # function takes in a maze represented by 2D list, and returns the length of the shortest path by points traveled over
    # taking into account one wall can be removed but doesnt have to be
    def answer(maze):
        # all potentially removable walls
        walls = removableWalls(maze)

        # distance with no walls removed
        shortestDistance = BFS(maze)

        # for: remove each removable wall
        # update shortest distance
        for wall in walls:
            # copy maze to maze2 and remove one wall from maze2
            maze2 = [x[:] for x in maze]
            maze2[wall[0]][wall[1]] = 0

            # store result to not have to run BFS again
            distance = BFS(maze2)

            # if this distance is shorter or shortestDistance does not have a real value
            if (distance != -1) and (distance < shortestDistance or shortestDistance == -1):
                shortestDistance = distance

        return shortestDistance


    # runtime
    # O(G(V,E))
    # =
    # O(|V|+|E|)
    # runtime proportional to number of edges + number of vertices, just like any BFS algorithm

    # function takes in a maze represented by 2D list, and returns the length of the shortest path by points traveled over
    # navigates from top right to bottom left of the 2D list
    def BFS(maze2):
        # variables used to break out of several loops
        find1 = False
        find2 = False

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

        # depth layer being currently explored
        currentLayer = set()
        currentLayer.add((0, 0))

        # all points we have already explored
        allExplored = set()
        allExplored.add((0, 0))

        # next layer to explore
        nextLayer = set()

        distance = 1

        # while the 2D list has not been fully explored
        # breaks used within to break from when exit is found
        # avoids infinite loop condition
        while (currentLayer != set()):

            # for each point in the current depth of the grid
            for point in currentLayer:
                # neighbors of point
                neighbors = navigableAdjacentPoints(maze2, point[0], point[1])

                for neighbor in neighbors:

                    # add neighbor to nextlayer
                    # only if neighbor was not previously explored
                    if neighbor not in allExplored and neighbor not in currentLayer:
                        nextLayer.add(neighbor)

                        # if neighbor is exit, break
                        if neighbor == (width - 1, height - 1):
                            find1 = True
                            break

                # if neighbor was exit, break again
                if find1 == True:
                    find2 = True
                    break
            # break again to exit loop
            if find2 == True:
                break

            # We have explored the current layer, concatenate explored with currentLayer
            allExplored |= currentLayer
            # we increment the current layer to the next layer
            currentLayer = nextLayer.copy()
            # we clear the next layer to explore
            nextLayer.clear()

            distance += 1

        # if no path exists, return -1
        if currentLayer == set():
            return -1

        # special case for 2x2
        if distance == 2:
            return 2

        # add 1 to travel over the exit
        return distance + 1


    # runtime
    # O(1)
    # always checks 4 grid squares
    # returns a set of navigable adjacent points to some point
    def navigableAdjacentPoints(maze, x, y):
        toRet = set()

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

        if x != 0:
            if maze[x - 1][y] == 0:
                toRet.add((x - 1, y))

        if x != width - 1:
            if maze[x + 1][y] == 0:
                toRet.add((x + 1, y))

        if y != 0:
            if maze[x][y - 1] == 0:
                toRet.add((x, y - 1))

        if y != height - 1:
            if maze[x][y + 1] == 0:
                toRet.add((x, y + 1))

        return toRet


        # returns list of tuples [(x,y),....(x,y)] representing coordinates with walls that could be removed
        # walls touching halls


    # runtime
    # O(maze points)
    # O(n) , defining n as width*heigth of maze

    # finds all walls worth removing in a maze
    # finds walls adjacent to passable space
    def removableWalls(maze):
        list_of_tuples = []

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

        wall = 1

        for i in range(0, width):
            for j in range(0, height):

                # if this grid is a wall
                if maze[i][j] == wall:

                    if i != 0:
                        if maze[i - 1][j] != wall:
                            list_of_tuples.append((i, j))

                    if i != (width - 1):
                        if maze[i + 1][j] != wall:
                            list_of_tuples.append((i, j))

                    if j != 0:
                        if maze[i][j - 1] != wall:
                            list_of_tuples.append((i, j))

                    if j != (height - 1):
                        if maze[i][j + 1] != wall:
                            list_of_tuples.append((i, j))

        # remove duplicates
        list_of_tuples = set(list_of_tuples)
        list_of_tuples = list(list_of_tuples)

        return list_of_tuples


maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

maze2 = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1],
         [0, 0, 0, 0, 0, 0]]

maze3 = [[0, 1], [1, 0]]

maze4 = [[0, 0, 0, 0, 0, ],
         [1, 1, 1, 1, 0],
         [0, 0, 0, 0, 0],
         [0, 1, 1, 1, 1],
         [0, 0, 0, 0, 0]]

maze5 = [[0, 0, 0, 0, 0, 0],
         [1, 1, 1, 1, 1, 0],
         [1, 1, 1, 1, 1, 1],
         [0, 0, 0, 0, 0, 0],
         [0, 1, 1, 1, 1, 1],
         [0, 0, 0, 0, 0, 0]]  # Answer 21

maze6 = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]  # Answer 7
maze7 = [[0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 1, 1, 0]]  # Answer 7
maze8 = [[0, 1, 1, 1], [0, 1, 0, 0], [1, 0, 1, 0], [1, 1, 0, 0]]  # Answer 7
maze9 = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1],
         [0, 0, 0, 0, 0, 0]]  # Answer 11

print(answer(maze))
print(answer(maze2))
print(answer(maze3))
print(answer(maze4))
print("asd")
print(answer(maze5))
print(answer(maze6))
print(answer(maze7))
print(answer(maze8))
print(answer(maze9))