迷宫最短路径问题

问题描述

给定一个迷宫，迷宫由 R 行 C 列（1 <= R, C <= 5）的格子组成。每个格子可以是：

• 空地 (.)，表示可以走
• 障碍物 (#)，表示不能走

从迷宫的左上角 (1,1) 出发，要求找到最少的步数到达右下角 (R,C)，只允许在水平方向和垂直方向上移动，不能斜着走。保证一定能够到达终点。

输入

• 第一行输入两个整数 R 和 C，表示迷宫的行数和列数。
• 接下来 R 行，每行有 C 个字符，表示迷宫的布局，字符可以是 . 或 #。

输出

• 输出从左上角到右下角的最少步数。

示例

输入：

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

输出：

9