Untitled

from queue import PriorityQueue

def get_maze_map(maze):
    min_row = 0
    min_col = 0
    max_row = len(maze) - 1
    max_col = len(maze[0]) - 1


    maze_map = {}
    for row in range(len(maze)):
        for col in range(len(maze[i])):
            empty_direction = {'D':0, 'T':0, 'N':0, 'B':0}
            if maze[row][col] != '#':
                maze_map[(row, col)] = empty_direction
                if col != max_col:
                    if maze[row][col+1] != '#':
                        maze_map[(row, col)]['D'] = 1
                if col != min_col:
                    if maze[row][col-1] != '#':
                        maze_map[(row, col)]['T'] = 1
                if row != max_row:
                    if maze[row+1][col] != '#':
                        maze_map[(row, col)]['N'] = 1
                if row != min_row:
                    if maze[row-1][col] != '#':
                        maze_map[(row, col)]['B'] = 1
    return maze_map

def manhattan_dist(cell1, cell2):
    x1,y1 = cell1;
    x2,y2 = cell2;
    return abs(x1-x2) + abs(y1-y2)

def a_star(maze, maze_map):
    rows = len(maze)
    cols = len(maze[0])

    start = (rows-1, cols-1)
    g_score = {cell:float('inf') for cell in maze_map}
    g_score[start] = 0
    f_score = {cell:float('inf') for cell in maze_map}
    f_score[start]=manhattan_dist(start,(0,0))

    queue = PriorityQueue()
    queue.put((manhattan_dist(start,(0,0)),manhattan_dist(start,(0,0)),start))
    aPath={}

    while not queue.empty():
        currCell = queue.get()[2]
        if currCell==(0,0):
            break

        for direc in 'DTNB':
            if maze_map[currCell][direc] == 1:
                if direc == 'D' and maze[currCell[0]][currCell[1]+1] != '#':
                    childCell=(currCell[0],currCell[1]+1)
                elif direc == 'T' and maze[currCell[0]][currCell[1]-1] != '#':
                    childCell=(currCell[0],currCell[1]-1)
                elif direc == 'N' and maze[currCell[0]+1][currCell[1]] != '#':
                    childCell=(currCell[0]+1,currCell[1])
                elif direc == 'B' and maze[currCell[0]-1][currCell[1]] != '#':
                    childCell=(currCell[0]-1,currCell[1])

                temp_g_score=g_score[currCell]+1
                temp_f_score=temp_g_score+manhattan_dist(childCell,(0,0))

                if temp_f_score < f_score[childCell]:
                    g_score[childCell]= temp_g_score
                    f_score[childCell]= temp_f_score
                    queue.put((temp_f_score,manhattan_dist(childCell,(0,0)),childCell))
                    aPath[childCell]=currCell
    if currCell != (0,0):
        return -1
    fwdPath={}
    cell=(0,0)
    while cell != start:
        fwdPath[aPath[cell]]=cell
        cell=aPath[cell]
    return len(fwdPath)

if __name__ == '__main__':
    m_row, n_col = map(int, input().split(" "))
    maze = []
    for i in range(m_row):
        maze.append([str(x) for x in input()])

    maze_map = get_maze_map(maze)
    result = a_star(maze, maze_map)
    print(result)