BFS

题目关键字

“走到出口所需要的最少步数”， 说明至少有一条路径是可以到达出口的，没有问方案数而是问最少的步数， 
所以我就选了BFS（广度优先搜索），而不是DFS

提前准备

1、迷宫数据数组
    因为题目输入迷宫数据的时候是直接每个字符挨在一起，根据python的特性
    直接使用一维数组 mg[n]， 每个成员就是一行迷宫数据

2、方向向量
    dx、dy， 组合在一起得到下一次前进的方向： 上、下、左、右

3、起点到某一点的距离表示
    二维数组 distance[n][m]， 对于distance的数据：
        -1：表示不可达例如distance[i][j]=-1，表示从起点 S 开始走， 
            对于mg[i][j]这个点是不可达的
        0： 表示可达
        >0: 表示起点到这个点的距离，同时表示已经访问过这个点了

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

    queue = []
    queue.append((x1, y1))
    distance[x1][y1] = 0  # 第一个点 起点S 肯定是可达的

    while queue:
        point = queue.pop(0)

        for i in range(4):  # 方向向量只有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:  # >0 表示距离->走过就不用走了
                continue
            if mg[next_x][next_y] == "#":
                continue
            # 下一点是终点，直接结束函数，距离就是上一个点的 + 1,要再跨一步才到终点
            if mg[next_x][next_y] == 'T': 
                return distance[point[0]][point[1]] + 1

            queue.append((next_x, next_y))  # 队列加入下一个点
            distance[next_x][next_y] = distance[point[0]][point[1]] + 1  # 下一个点的距离


if __name__ == "__main__":

    # 方向向量， 上、下、左、右， 表示在数组中移动
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    n, m = map(int, input().split())
    mg = [input() for _ in range(n)]  # 迷宫数据
    distance = [[-1] * m for _ in range(n)]  # 定义并初始化距离数组

    for i in range(len(mg)):
        for j in range(len(mg[i])):
            if mg[i][j] == "S":
                res = bfs(i, j)
                print(res)
                break  # 这里直接braek，剩下的遍历是多余的，因为只能从S开始