#420. 迷宫

迷宫

迷宫

题目描述

一个迷宫由 RR 行 CC 列的格子组成,有的格子里有障碍物,不能通行;有的格子是空地,可以通行。

给定一个 R×CR\times C 大小的迷宫,空地格子用 . 表示,有障碍物的格子用 # 表示。

求从左上角(第 11 行第 11 列)走到右下角(第 RR 行第 CC 列)最少需要走多少步。每步只能向上、下、左、右四个方向移动一格,不能斜着走,也不能走出迷宫或进入障碍物。

数据保证起点、终点均为空地,且一定存在从起点到终点的路径。若起点和终点是同一个格子,则答案为 00。

输入格式

第一行包含两个整数 R,CR,C,分别表示迷宫的行数和列数。

接下来 RR 行,每行包含一个长度为 CC 的字符串,仅由 . 和 # 组成,表示迷宫。

输出格式

输出一个整数,表示从左上角走到右下角的最少步数。

样例 1

3 3
...
.#.
...
4

样例 2

1 1
.
0

数据范围与提示

对于本题所提供的测试数据:1≤R,C≤10001\le R,C\le 1000,并且 R×C≤106R\times C\le 10^6。

  • 每走到相邻的一格计为 11 步,起点不计步数。
  • 数据保证可以走到终点。
  • 建议使用**广度优先搜索(BFS)**求无权网格图的最短路;普通 DFS 不保证在大数据下能及时找到最短路。