Wall breaking

A labyrinth has two kinds of wall squares: walls at the border of the labyrinth are marked with # and internal walls are marked with *. You can break an internal wall to open new routes through the labyrinth.

Your task is to find a route from the square A to the square B. In each step, you can move horizontally or vertically to an adjacent square. What is the smallest number of walls that you need to break?

In a file breakwall.py, implement the function find_route that returns the smallest number of walls to break.

def find_route(grid):
    # TODO

if __name__ == "__main__":
    grid = ["########",
            "#*A*...#",
            "#.*****#",
            "#.**.**#",
            "#.*****#",
            "#..*.B.#",
            "########"]
    print(find_route(grid)) # 2

In this labyrinth, you can move one step to the left, four steps down, and four steps to the right. This route has two walls that must be broken.