BFS 广度优先搜索

与DFS比较直观的区别是， BFS不会一遇到一个满足的点就会继续搜索，而是先搜集它附近
满足的点放在一个队列中，然后按照队列的特点往下进行

# coding:utf-8
# yang


def bfs(x1, y1):
    global mg, distance, queue, dx, dy

    queue.append((x1, y1))  # 入队
    distance[x1][y1] = 0

    while queue:
        point = queue.pop(0)

        for i in range(4):
            next_x, next_y = point[0] + dx[i], point[1] + dy[i]

            if (next_x < 0 or next_x >= n) or (next_y < 0 or next_y >= m):  # 不能越界
                continue
            if distance[next_x][next_y] > 0:  # 走过不用走
                continue
            if mg[next_x][next_y] == '#':  # 有障碍物不能走
                continue

            queue.append((next_x, next_y))
            distance[next_x][next_y] = distance[point[0]][point[1]] + 1

    return distance[-1][-1]



if __name__ == "__main__":

    # 方向向量
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    n, m = map(int, input().strip().split())
    mg = [input().strip() for _ in range(n)]  # 存迷宫状态

    #从起点开始，对于某一个点 -1表示不可达， 0表示可达，大于0表示距离
    distance = [[-1] * m for _ in range(n)]  
    queue = []

    res = bfs(0, 0)
    print(res + 1)  # 起点也算