CCC'2020J5/S2逃脱房间问题的解决方法（Python）

逃脱房间问题是一道需要使用 BFS（广度优先搜索）算法解决的典型问题。思路是在一个矩阵中模拟人员的行动，找到从起点到终点的最短路径。

首先，我们需要读取输入数据，并将其转化为一个字符串矩阵。每个房间的状态可以用一个字符表示。例如，'#' 表示墙，'.' 表示通道，'S' 表示起点，'F' 表示终点。

接下来，我们需要使用 BFS 算法搜索从起点到终点的最短路径。我们需要一个队列来存储搜索的状态。队列中的每个节点表示一个当前位置和它到起点的距离。首先，我们将起点加入队列并标记为已访问，然后我们继续弹出队列中的每个位置，并且将它相邻的、未访问的位置添加到队列中。我们还需要记录每个位置的前一个位置（即距离最短的路径的前一个位置）。当我们到达终点时，我们可以通过回溯来找到最短路径。

下面是具体的 Python 代码实现，代码中的 comments（注释）有助于更好地理解算法过程：

# 读取输入数据
n, m = map(int, input().split())
maze = [input() for _ in range(n)]

# 定义起点和终点
start, end = None, None
for i in range(n):
    for j in range(m):
        if maze[i][j] == 'S':
            start = (i, j)
        elif maze[i][j] == 'F':
            end = (i, j)

# 广度优先搜索
visited =