题目：走出迷宫的最少步数

任务总览

题目描述

一个迷宫由 R × C 的格子组成：

• 空地 用 '.' 表示，可以走。
• 障碍物 用 '#' 表示，不能走。
• 只能 上下左右 四个方向移动，不能斜着走。
• ​目标​：从左上角 (0, 0) 走到右下角 (R-1, C-1)​的最短路径步数​。

数据保证一定可以走到终点。

输入格式

1. ​第一行​：包含两个整数 R 和 C（1 ≤ R, C ≤ 40），表示迷宫的行数和列数。
2. ​接下来的 R 行​：
   • 每行包含 C 个字符，描述迷宫的地图。
   • '.' 表示空地，'#' 表示障碍物。
   • ​**保证 (0,0) 和 (R-1,C-1) 都是 '.'**​。

输出格式

• 输出一个整数，表示最少需要经过多少步才能从 (0,0) 走到 (R-1,C-1)。
• ​步数包括起点和终点​。

输入输出示例

输入示例

5 5
..###
#....
#.#.#
#.#.#
#.#..

输出示例

9

题目分析

本题是一个典型的 最短路径 问题，适合使用 ​**广度优先搜索（BFS）**​：

1. ​广度优先搜索（BFS）特点​：
   • BFS 适用于 ​无权图的最短路径​，即每次移动的代价相同。
   • 队列 结构保证了先入先出，能找到最短路径。
   • 适用于 ​网格搜索问题​。
2. ​搜索方式​：
   • 从 (0,0) 开始，每次向 四个方向（上、下、左、右） 移动。
   • 记录已经访问过的位置，避免重复搜索。
   • 直到到达 (R-1, C-1)，输出步数。
3. ​时间复杂度​：
   • BFS 的时间复杂度是 ​**O(R × C)**​，在 R, C ≤ 40 时运行效率良好。

解法

方法：广度优先搜索（BFS）

• 使用队列（queue）存储当前位置 和 ​步数​。
• ​方向数组​：
  • 右：(0, 1)
  • 左：(0, -1)
  • 下：(1, 0)
  • 上：(-1, 0)
• ​步骤​：
  1. ​将起点 (0,0) 入队​，步数设为 1。
  2. ​逐层扩展​，每次移动到​可行​（'.' 且未访问）的相邻位置。
  3. ​当访问到 (R-1, C-1) 时，输出步数​。

时间复杂度分析

由于 R, C ≤ 40，O(R × C) 可接受，BFS 是最优解法。